LeetCode 從零單刷：Intersection of Two Linked Lists - 兩鏈表交點

題目大意

給定兩個單鏈表頭節點 headA、headB，找到它們的第一個公共節點（按引用比較，非值）。若無交點返回 null。要求 O(n) 時間、O(1) 空間，且不得破壞鏈表結構。

核心思路：長度差對齊

若兩鏈表長度相同，同步遍歷即可在交點相遇。長度不同則先讓長鏈表的指針前進「長度差」步，然後同步走。具體步驟：

1. 遍歷兩鏈表分別得長度 lenA、lenB。
2. 指針 pA、pB 重新指向頭節點。
3. 若 lenA > lenB，pA 先走 lenA - lenB 步；反之 pB 先走差值步。
4. 同步移動 pA、pB，首次 pA == pB 即為交點（含 null）。

代碼實現 (C++)

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA = headA, *pB = headB;
        int lenA = 0, lenB = 0;
        while (pA) { ++lenA; pA = pA->next; }
        while (pB) { ++lenB; pB = pB->next; }

        pA = headA; pB = headB;
        if (lenA > lenB) {
            int diff = lenA - lenB;
            while (diff--) pA = pA->next;
        } else {
            int diff = lenB - lenA;
            while (diff--) pB = pB->next;
        }

        while (pA) {
            if (pA == pB) return pA;
            pA = pA->next;
            pB = pB->next;
        }
        return nullptr;
    }
};

另一種優雅寫法：雙指針循環遍歷

讓 pA 走完 A 後轉到 B 頭，pB 走完 B 後轉到 A 頭。兩指針走過的總長度均為 lenA + lenB，必在交點或 null 相遇。代碼極簡：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pA = headA, *pB = headB;
    while (pA != pB) {
        pA = pA ? pA->next : headB;
        pB = pB ? pB->next : headA;
    }
    return pA; // 相等時要么是交點，要么同時為 nullptr
}

複雜度

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

總結

本題考察鏈表基本操作與指針技巧。「長度差對齊」邏輯清晰，適合面試講解；「雙指針循環」代碼極短且無需額外變數，屬於進階技巧。建議兩種都會，面試先寫對齊版，再補充循環版作為優化。