LeetCode 160 Intersection of Two Linked Lists：雙指針法求交點

題目大意

給兩個單鏈表頭節點，求它們相交的起始節點（引用相同，非值相同）。無交點返回 null。要求 O(n) 時間，O(1) 空間，不修改鏈表。

核心技巧：長度差對齊 + 同步遍歷

1. 遍歷兩鏈表得長度 `lenA`, `lenB`。
2. 長鏈表指針先走 `|lenA - lenB|` 步，使兩指針到尾部剩餘長度相等。
3. 同步向後遍歷，首次 `pA == pB` 即為交點（或同為 null 表示無交點）。

代碼

/**
 * 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 nullptr;
        int lenA = 0, lenB = 0;
        ListNode *p = headA, *q = headB;
        while (p) { ++lenA; p = p->next; }
        while (q) { ++lenB; q = q->next; }
        p = headA; q = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; ++i) p = p->next;
        } else {
            for (int i = 0; i < lenB - lenA; ++i) q = q->next;
        }
        while (p != q) {
            p = p->next;
            q = q->next;
        }
        return p; // 可能為 nullptr
    }
};

替代優雅寫法：雙指針循環遍歷

指針 `pA`, `pB` 分別從 headA, headB 出發，走到末尾則跳轉到另一鏈表頭部。兩指針必在第二次遍歷時相遇（交點或 null）。代碼極短：

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

複雜度

• 時間：O(n+m)。
• 空間：O(1)。

總結

Intersection of Two Linked Lists 是鏈表雙指針經典題。**長度差對齊** 邏輯清晰；**循環遍歷** 代碼極短且無需顯式計算長度。兩種寫法均為 O(1) 空間，面試必備。