程式設計師編程藝術：第九章——鏈表追趕問題全解析

編輯：關於C語言

前言：從機器人追趕到鏈表指針舞蹈

微軟亞洲研究院曾出過一道經典題目：在一條直線軌道上放置兩個機器人，只能使用「左移、右移、條件判斷（對方是否來過）、無條件跳轉」四條指令，編寫同一個程式讓兩機器人必定相遇。這本質上是「追趕問題」的離散化版本，而在資料結構領域，鏈表上的雙指針追趕技巧正是此思想的直接體現。本章將系統講解鏈表倒數第 k 節點、兩鏈表相交判斷、環檢測等核心問題，並提供生產級代碼範本。

第一節：求鏈表倒數第 k 個節點

問題定義

輸入單向鏈表頭指針與整數 k，輸出倒數第 k 個節點（倒數第 0 個為尾節點）。

核心思想：快慢指針保持固定距離

雙指針 p1, p2 同指向頭節點
p2 先向前走 k 步
若走不到 k 步（p2 為 NULL），說明 k > 鏈表長度，返回 NULL
雙指針同步前進，直到 p2 走到末尾
此時 p1 指向倒數第 k 個節點

生產級代碼實現

struct ListNode {
    char data;
    ListNode* next;
};

// 返回倒數第 k 個節點，k >= 0；若 k 超出長度返回 nullptr
ListNode* findKthFromEnd(ListNode* head, int k) {
    assert(k >= 0);
    ListNode *p1 = head, *p2 = head;

    // p2 先走 k 步
    for (; k > 0 && p2 != nullptr; --k) {
        p2 = p2->next;
    }
    if (k > 0) return nullptr;  // 鏈表長度 < k

    // 同步前進
    while (p2 != nullptr) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

擴展思考

若鏈表為雙向鏈表，可直接從尾節點倒數
若鏈表可能有環，需先檢測環並處理
此模式廣泛應用於：合併兩有序鏈表、檢測回文鏈表、LRU Cache 淘汰邏輯

第二節：判斷兩個單向鏈表是否相交

問題定義

給定兩單向鏈表頭指針 h1, h2，判斷是否相交（共享同一節點記憶體地址），假設無環。

三種解法複雜度對比

方法	時間複雜度	空間複雜度	核心思想
雙重迴圈暴力	O(m×n)	O(1)	逐節點比對
Hash Set 記錄	O(m+n)	O(m)	空間換時間
尾節點比對（最優）	O(m+n)	O(1)	相交則尾節點必同

最優解法代碼

// 返回相交節點，不相交返回 nullptr
ListNode* getIntersectionNode(ListNode* h1, ListNode* h2) {
    if (!h1 || !h2) return nullptr;

    ListNode *p1 = h1, *p2 = h2;
    int len1 = 0, len2 = 0;

    // 計算長度並獲取尾節點
    while (p1->next) { p1 = p1->next; ++len1; }
    while (p2->next) { p2 = p2->next; ++len2; }

    // 尾節點不同 → 不相交
    if (p1 != p2) return nullptr;

    // 重置指針，長鏈表先走差值步
    p1 = h1; p2 = h2;
    if (len1 > len2) {
        for (int i = 0; i < len1 - len2; ++i) p1 = p1->next;
    } else {
        for (int i = 0; i < len2 - len1; ++i) p2 = p2->next;
    }

    // 同步前進尋找相交點
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

第三節：鏈表環檢測與相交判斷（含環情況）

Floyd 判圈算法（龜兔賽跑）

快指針每次 2 步，慢指針每次 1 步，若有環必相遇。


// 返回值：pair
pair detectCycle(ListNode* head) {
    if (!head || !head->next) return {false, head};

    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next && slow != fast) {
        slow = slow->next;
        fast = fast->next->next;
    }

    if (slow == fast) return {true, slow};   // 有環，返回相遇節點
    return {false, (fast ? fast : slow)};    // 無環，返回尾節點
}

帶環鏈表相交判斷完整邏輯

分別檢測兩鏈表是否有環，獲取 (has_cycle1, node1), (has_cycle2, node2)
若一環一無環 → 必不相交
若皆無環 → 用尾節點比對法
若皆有環：
- 若 node1 == node2 → 相交於環外或環上
- 否則從 node1->next 遍歷環，若遇到 node2 → 相交於環上（共用同一環）
- 否則 → 不相交（兩獨立環）

bool listsIntersect(ListNode* h1, ListNode* h2) {
    auto [c1, n1] = detectCycle(h1);
    auto [c2, n2] = detectCycle(h2);

    if (c1 != c2) return false;  // 一環一無環

    if (!c1) {  // 皆無環
        // 復用無環相交判斷邏輯（比對尾節點）
        ListNode *t1 = h1, *t2 = h2;
        while (t1->next) t1 = t1->next;
        while (t2->next) t2 = t2->next;
        return t1 == t2;
    }

    // 皆有環
    if (n1 == n2) return true;  // 相遇點相同

    // 檢查 n2 是否在 n1 的環上
    ListNode* cur = n1->next;
    while (cur != n1) {
        if (cur == n2) return true;
        cur = cur->next;
    }
    return false;
}

第四節：機器人相遇問題的數學本質

回到開頭的機器人問題：兩機器人初始位置任意，執行同一程式。解法關鍵在於「打破對稱性」：

// 伪代碼
LOOP:
    MOVE_LEFT
    IF OTHER_VISITED_HERE THEN GOTO MEET
    MOVE_RIGHT
    MOVE_RIGHT
    IF OTHER_VISITED_HERE THEN GOTO MEET
    GOTO LOOP

MEET:
    // 相遇邏輯
    HALT

核心洞見：通過「左移 1、右移 2」的非對稱移動模式，確保兩機器人相對速度非零，最終在有限軌道上必相遇。這與 Floyd 判圈算法「快慢指針」異曲同工——都是利用速度差打破對稱性，保證有限狀態空間內必相遇。

總結與避坑清單

問題	關鍵技巧	常見錯誤
倒數第 k 節點	雙指針固定間距	未檢查 k > 長度；k=0 語義混淆
兩鏈表相交（無環）	尾節點比對 + 長度對齊	混淆「值相等」與「指針相等」；修改原鏈表
環檢測	Floyd 算法	fast 指針越界未判空；相遇點非入口點
帶環相交	分類討論 + 環遍歷	忽略「共用同一環但入口不同」情況