鏈表追趕問題全解析：從倒數第 k 節點到環相交判斷，再到微軟機器人智力題

前言：機器人相遇智力題

水平軌道兩點放兩機器人，同一程序控制，指令：左/右移一步、條件判斷(對方曾到過此處?)、無條件跳轉。目標：必相遇。
這是去年微軟工程院題，本質是追趕問題，鏈表中經典體現為「快慢指針」。

一、鏈表倒數第 k 個節點

雙指針 p1, p2 起始指頭，p2 先走 k 步，再同步前進，p2 到尾時 p1 即為倒數第 k。
代碼：

ListNode* fun(ListNode* head, int k) {
    ListNode *p1 = head, *p2 = head;
    for (int i = 0; i <= k-1; i++) p2 = p2->next;
    while (p2) { p1 = p1->next; p2 = p2->next; }
    return p1;
}

靈感源自長跑：領先者與落後者速度差決定追上時間。平時多觀察生活、多思考，面試直覺自然來。

二、判斷兩單鏈表是否相交（無環）

1. 暴力 O(N²)：雙重循環。
2. Hash 表 O(N) 時間、O(N) 空間。
3. 尾節點法 O(N) 時間、O(1) 空間：無環相交 ⇒ 尾節點必相同。遍歷兩表記尾節點，比較即可。

三、帶環鏈表相交判斷

先判環（快慢指針）：

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

綜合邏輯：
1. 都無環 → 比尾節點。
2. 都有環 → 取一表相遇節點，看是否在另一表上（遍歷另一表或再跑快慢指針）。在 → 相交；不在 → 不相交。
3. 一有環一無環 → 不可能相交。

四、微軟機器人智力題答案

偽代碼：

start:
if (at position other NOT reached) move_right
if (at position other reached)     move_right; move_right
goto start

解析：
A 後 B 前，同速右移。A 到達 B 起點前，兩者均滿足第一條 → 同速。
A 到達 B 起點後，A 滿足第二條 → 雙速；B 仍滿足第一條 → 單速。
相對速度 = 1 步/單位時間，距離 |AB|，需 |AB| 時間追上。
細節：第二分支連續兩 move_right 不一定能精確雙速（指令原子性），但邏輯成立。

總結

追趕思想貫穿：倒數第 k、環檢測、相交判斷、機器人相遇。核心是速度差產生相對運動，快慢指針是時間換空間的藝術。