Find the node at which the intersection of two singly linked lists begins.
For example,
begin to intersect at node c1
.
NOTE: if the two linked lists do not intersect, return null
.
Here's the elegant solution to this question:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode a = headA;
ListNode b = headB;
while( a != b){
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
You might be quite confused with the solution here, but don't worry, we will get through it together visually! Credits to BryanBo-Cao for the visual graph effort!
Case 1 (have intersection and same length):
a
A: a1 → a2 → a3
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
b
-----------------------------------------
a
A: a1 → a2 → a3
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
b
-----------------------------------------
a
A: a1 → a2 → a3
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
b
-----------------------------------------
A: a1 → a2 → a3
↘ a
c1 → c2 → c3 → null
↗ b
B: b1 → b2 → b3
Since a == b
, we exit the while loop and return the intereaction node a = c1
.
Case 2 (have intersection and different length):
a
A: a1 → a2
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
b
-----------------------------------------
a
A: a1 → a2
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
b
-----------------------------------------
A: a1 → a2
↘ a
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
b
-----------------------------------------
A: a1 → a2
↘ a
c1 → c2 → c3 → null
↗ b
B: b1 → b2 → b3
-----------------------------------------
A: a1 → a2
↘ a
c1 → c2 → c3 → null
↗ b
B: b1 → b2 → b3
-----------------------------------------
A: a1 → a2
↘ a = null, then a = b1
c1 → c2 → c3 → null
↗ b
B: b1 → b2 → b3
-----------------------------------------
A: a1 → a2
↘
c1 → c2 → c3 → null
↗ b = null, then b = a1
B: b1 → b2 → b3
a
-----------------------------------------
b
A: a1 → a2
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
a
-----------------------------------------
b
A: a1 → a2
↘
c1 → c2 → c3 → null
↗
B: b1 → b2 → b3
a
-----------------------------------------
A: a1 → a2
↘ b
c1 → c2 → c3 → null
↗ a
B: b1 → b2 → b3
Since a == b
, we exit the while loop and return the intereaction node a = c1
.
Case 3 (have no intersection and same length):
a
A: a1 → a2 → a3 → null
B: b1 → b2 → b3 → null
b
-----------------------------------------
a
A: a1 → a2 → a3 → null
B: b1 → b2 → b3 → null
b
-----------------------------------------
a
A: a1 → a2 → a3 → null
B: b1 → b2 → b3 → null
b
-----------------------------------------
a = null
A: a1 → a2 → a3 → null
B: b1 → b2 → b3 → null
b = null
Since a == b
, we exit the while loop and return the intereaction node a = null
.
Case 4 (have no intersection and different length):
a
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
b
-----------------------------------------
a
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
b
-----------------------------------------
a
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
b
-----------------------------------------
a
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
b = null, then b = a1
-----------------------------------------
b a = null, then a = b1
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
-----------------------------------------
b
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
a
-----------------------------------------
b
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
a
-----------------------------------------
b
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
a
-----------------------------------------
b = null
A: a1 → a2 → a3 → a4 → null
B: b1 → b2 → b3 → null
a = null
Since a == b
, we exit the while loop and return the intereaction node a = null
.
Well, that will be all for today. See you next time!
Post was published on , last updated on .
Like the content? Support the author by paypal.me!