Find the node at which the intersection of two singly linked lists begins.

For example,

linked-list-intersection-1

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!