160. 相交鏈表

思路

先得到兩個鏈表長度的區別diff，若大於 0 表示鏈表一比較長，否則鏈表二比較長。
cur1固定指向比較長的鏈表，先走出abs(diff)步，
之後兩個指針一起前進，當相同時就表示相會，得到答案。

程式碼

鏈表

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr) return nullptr;
        int diff = 0;
        ListNode *cur1 = headA;
        ListNode *cur2 = headB;
        while(cur1 != nullptr) { ++diff; cur1 = cur1 -> next; }
        while(cur2 != nullptr) { --diff; cur2 = cur2 -> next; }
        if(cur1 != cur2) return nullptr; // 無交集
        if(diff < 0) { // headB 比較長
            cur1 = headB; 
            cur2 = headA; 
        }
        else { // headA 比較長
            cur1 = headA;
            cur2 = headB; 
        }
        diff = abs(diff);
        while(diff--) {
            cur1 = cur1 -> next;
        }
        while(cur1 != cur2) {
            cur1 = cur1 -> next;
            cur2 = cur2 -> next;
        }
        return cur1;
    }
};

複雜度分析

• 時間複雜度：$O(L)$
• 空間複雜度：$O(1)$