Problem description:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

1
2
3
4
5
6
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Solution:

Question to ask:

  1. If one of them is NULL? both NULL? should return NULL?

If two linked list have intersetion, we can divide it into two situation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
example 1: same length of A, B
    A1->A2->C1->C2->C3
    B1->B2->C1->C2->C3
    will meet in first iteration
    
example 2: diff length of A, B
    A1->A2->A3->C1->C2->C3
    B1->B2->C1->C2->C3
    
    let B go from A after it meets NULL,
    A1->A2->A3->C1->C2->C3->B1->B2->C1->C2->C3
    B1->B2->C1->C2->C3->A1->A2->A3->C1->C2->C3
                                    |
                                    will meet in second iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return NULL;
        
        ListNode *p1= headA, *p2= headB;
        while(p1 && p2 && p1!=p2){ //this contains if they are intersect in first node
            p1= p1->next;
            p2= p2->next;
            if(p1 == p2) return p1;
            
            if(!p1) p1= headA;
            if(!p2) p2= headB;
        }
        return p1;
    }
};

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/gu3Huw