LeetCode 160 Intersection of Two Linked Lists：長度對齊法求交點

問題描述

給定兩個單鏈表頭節點，找到它們的交點（引用相同，非值相同）。無交點返回 null。要求 O(n) 時間、O(1) 空間，保持原結構不變。

核心思路：長度差對齊

1. 遍歷兩表得長度 lenA, lenB
2. 長表指針先走 |lenA-lenB| 步
3. 兩指針同步前進，首次相遇即為交點

原理：對齊後，兩指針到交點距離相等，若無交點最終同為 null。

完整代碼

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (!headA || !headB) return nullptr;
        
        // 1. 計算長度
        int lenA = 1, lenB = 1;
        ListNode *pA = headA, *pB = headB;
        while (pA->next) { ++lenA; pA = pA->next; }
        while (pB->next) { ++lenB; pB = pB->next; }
        
        // 2. 快速判斷無交點：尾節點不同
        if (pA != pB) return nullptr;
        
        // 3. 對齊起點
        pA = headA; pB = headB;
        if (lenA > lenB) {
            int diff = lenA - lenB;
            while (diff--) pA = pA->next;
        } else if (lenB > lenA) {
            int diff = lenB - lenA;
            while (diff--) pB = pB->next;
        }
        
        // 4. 同步查找
        while (pA != pB) {
            pA = pA->next;
            pB = pB->next;
        }
        return pA;  // 交點或 null
    }
};

關鍵細節

• 尾節點比較：`pA != pB` 直接判無交點，省去後續遍歷
• 長度計算包含頭節點：初始值 1，而非 0
• 同步循環條件：`pA != pB` 涵蓋找到交點、同為 null 兩種情況
• 不修改結構：僅移動指針，滿足題目要求

替代方案：雙指針「環形」遍歷（更優雅）

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return nullptr;
    ListNode *pA = headA, *pB = headB;
    while (pA != pB) {
        pA = pA ? pA->next : headB;
        pB = pB ? pB->next : headA;
    }
    return pA;
}

原理：pA 走完 A 再走 B，pB 走完 B 再走 A，總長度均為 lenA+lenB，必在交點或 null 相遇。代碼極簡，無需顯式計算長度。

複雜度

• 時間：O(lenA + lenB)
• 空間：O(1)