### 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) {

return null;
}

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!