經典鏈表面試題：判斷環與尋找中間節點（快慢指針法）

題目一：判斷單鏈表是否存在環（搜狗面試題）

方法一：雙指針異步遍歷（理解用）

指針 p 正常遍歷，指針 q 每次從頭節點出發走到 p 當前位置，比較步數。若步數不一致，說明存在環。

方法二：快慢指針（標準解法）

slow 每次走 1 步，fast 每次走 2 步。若鏈表有環，兩指針必會在環內相遇（slow == fast）；若 fast 到達 nullptr 則無環。

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

題目二：查找未知長度單鏈表的中間節點（騰訊面試題）

方法一：兩次遍歷（直觀但低效）

先遍歷求長度 n，再走到 n/2 位置。

方法二：快慢指針（一遍遍歷，最優）

slow 走 1 步，fast 走 2 步。當 fast 到達末尾時，slow 恰好在中間。

ListNode* findMiddle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  // 偶數節點返回偏右的中間節點
}

總結

快慢指針（Floyd 判圈算法）是解決鏈表環檢測、中間節點、倒數第 K 個節點等問題的利器，時間 O(n)、空間 O(1)，面試必備。

本文出自「驛落黃昏」博客，轉載請保留出處：原文鏈接