互聯網大廠 C/C++ 面試精選：鏈表相交、環檢測與公共節點經典算法

題目一：判斷兩個單鏈表是否相交

核心洞察

若兩單鏈表相交，則從第一個公共節點起，後續所有節點完全共享，因此尾節點必然相同。

算法流程

1. 遍歷鏈表 A 獲取長度 lenA 和尾節點 tailA
2. 遍歷鏈表 B 獲取長度 lenB 和尾節點 tailB
3. 比較 tailA == tailB：相同則相交，不同則不相交

複雜度

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

題目二：找到第一個公共節點

對齊遍歷法（推薦）

1. 獲取兩表長度 lenA、lenB，假設 lenA > lenB
2. 長表指針先走 lenA - lenB 步
3. 雙指針同步前進，首次相遇節點即為第一個公共節點

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) return NULL;

    // 1. 計算長度
    int lenA = 0, lenB = 0;
    ListNode *pA = headA, *pB = headB;
    while (pA) { lenA++; pA = pA->next; }
    while (pB) { lenB++; pB = pB->next; }

    // 2. 對齊起點
    pA = headA; pB = headB;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) pA = pA->next;
    } else {
        for (int i = 0; i < lenB - lenA; i++) pB = pB->next;
    }

    // 3. 同步查找
    while (pA != pB) {
        pA = pA->next;
        pB = pB->next;
    }
    return pA;  // 可能為 NULL（不相交）
}

進階變體：只能遍歷一次且可修改鏈表

思路：將鏈表 A 尾節點指向頭節點形成環，問題轉化為「檢測鏈表 B 環入口」，最後恢復鏈表 A。詳見原文鏈接。

題目三：判斷鏈表是否有環

快慢指針法

• slow 每次 1 步，fast 每次 2 步
• 若有環，必在環內相遇（slow == fast）
• 若 fast 到達 NULL，無環

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;
}

數學證明

設環長 L，入口距頭 a，相遇點距入口 x。fast 走 2(a+x)，slow 走 a+x，差值 a+x = kL → 必相遇。

題目四：找出環的入口節點

雙指針二次相遇法

1. 快慢指針首次相遇（確認有環）
2. slow 重置為頭節點，fast 保持在相遇點
3. 雙指針同速（各 1 步）前進，再次相遇點即為環入口

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    // 1. 尋找相遇點
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return NULL;  // 無環

    // 2. 尋找入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

原理推導

首次相遇時：slow 走 a + x，fast 走 2(a + x) = a + x + kL → a + x = kL → a = kL - x。
第二階段：slow 從頭走 a 到入口，fast 從相遇點走 a = kL - x 正好也到入口（繞環 k-1 圈）。

面試加分項

總結

鏈表相交與環問題是指針操作、邊界思維、數學建模的綜合考察。掌握尾節點判相交、長度差對齊找公共節點、快慢指針檢測環與找入口三大核心模板，並能清晰推導數學原理，是通過大廠算法面試的關鍵。建議在 LeetCode 160、141、142 題上反覆練習至盲打無誤。