LeetCode 160. 相交鏈表：雙指針長度對齊法 C 語言解法詳解

LeetCode 160. 相交鏈表：雙指針長度對齊法 C 語言解法詳解

找到兩個單鏈表相交的起始節點。本文詳解「先求長度、長鏈表先走差值步、雙指針同步前進」的 O(n) 時間 O(1) 空間標準解法，並提供無需求長度的雙指針巧法（雙倍遍歷）作為進階拓展。

題目大意

• 輸入：兩單鏈表頭 `headA`、`headB`。
• 相交定義：從某節點開始，**引用相同**（非值相同），即 `nodeA == nodeB`。
• 輸出：相交起始節點指針，無相交返回 `NULL`。
• 約束：無環、保持原結構、O(n) 時間、O(1) 空間。

方法一：長度對齊法（標準教學解）

1. 遍歷兩鏈表得長度 `lenA`、`lenB`。
2. 長鏈表指針先走 `|lenA - lenB|` 步，使兩指針距尾部等遠。
3. 雙指針同步前進，首次相等即為相交節點（或同為 `NULL`）。

C 語言實現（長度對齊）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *pA = headA, *pB = headB;
    int lenA = 0, lenB = 0;

    // 1. 計算長度
    while (pA) { lenA++; pA = pA->next; }
    while (pB) { lenB++; pB = pB->next; }

    // 2. 重置指針
    pA = headA; pB = headB;

    // 3. 長鏈表先走差值步
    if (lenA > lenB) {
        int diff = lenA - lenB;
        while (diff--) pA = pA->next;
    } else {
        int diff = lenB - lenA;
        while (diff--) pB = pB->next;
    }

    // 4. 同步前進尋找相交
    while (pA && pB) {
        if (pA == pB) return pA; // 找到相交節點
        pA = pA->next;
        pB = pB->next;
    }
    return NULL; // 無相交
}

方法二：雙指針雙倍遍歷法（無需求長度，極其優雅）

**核心思想**：指針 `pA` 走完 `A` 再走 `B`，`pB` 走完 `B` 再走 `A`。若相交，兩指針走過總長度相同（`lenA + lenB - lenCommon`），必在相交點相遇；若不相交，同為 `NULL` 相遇。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *pA = headA, *pB = headB;
    if (!pA || !pB) return NULL;

    while (pA != pB) {
        pA = pA ? pA->next : headB; // 走完A轉入B
        pB = pB ? pB->next : headA; // 走完B轉入A
    }
    return pA; // 相交節點或NULL
}

兩方法對比

關鍵點與陷阱

• 相交判斷是指針地址相等：`pA == pB`，而非 `pA->val == pB->val`。
• 無環保證：題目保證無環，否則雙倍遍歷法會死循環。
• 保持原結構：僅讀取指針，不修改 `next`，符合要求。
• 空鏈表處理：雙倍遍歷法開頭判空可避免無限循環（雖然 `while(pA!=pB)` 配合條件移動天然處理）。

測試用例

// 相交情況
A: 1→2→3
           ↘
             6→7→NULL
           ↗
B:     4→5
相交節點：6

// 無相交
A: 1→2→3→NULL
B: 4→5→NULL
返回：NULL

// 一鏈表為空
A: NULL
B: 1→2→NULL
返回：NULL

總結

相交鏈表問題通過**長度對齊**或**對稱雙倍遍歷**完美解決。面試建議：先寫長度對齊法展示扎實基本功，再補充雙倍遍歷法體現進階思維。理解「指針地址相等即相交」是核心，切勿混淆為值相等。