160. Intersection of Two Linked Lists

發表於 | 分類於

problem

solution

option 1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *a = headA, *b = headB;
        while(a!=b){
            if(!a) a= headB;
            else a= a->next;
            if(!b) b = headA;
            else b=b->next;
        }
        return a;
    }
};

option 2

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
26
27
28
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 1. 是否有相同終點以判斷是否有交集
        // 2. 如果有交集，讓長串列先走幾步
        int lenA = 0, lenB= 0;
        ListNode *a = headA, *b = headB;
        while(a){
            a=a->next;
            lenA++;
        }
        while(b){
            b=b->next;
            lenB++;
        }
        // no cycle
        if(a!=b) return nullptr;
        ListNode *fast = (lenA>=lenB)?headA:headB;
        ListNode *slow = (lenA<lenB)?headA:headB;
        int n = abs(lenA-lenB);
        while(n--) fast = fast->next;
        while(fast!=slow){
            slow=slow->next;
            fast = fast->next;
        }
        return slow; 
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)