环形链表 II 图解题解

这道题比判断有环多问了什么

LeetCode 141 只问链表里有没有环，快慢指针一相遇就能返回 true。本题要的更多：把环的入口节点找出来，也就是链表从哪个节点开始绕圈；若无环则返回 null。直观的做法是哈希集合——边走边把访问过的节点存进集合，第一个重复见到的节点就是入口，时间 O(n) 但空间也是 O(n)。进阶目标是不开任何额外结构，只靠几个指针把入口逼出来。

快慢指针为什么一定相遇，不会互相跳过

slow 每次走一步、fast 每次走两步。只要有环，两个指针迟早都会进环，此后每一轮 fast 与 slow 的距离恰好缩短一步——一步一步逼近，不存在「跨过去错过了」的可能，所以必然在环内某个位置相遇。若无环，fast 会先撞到 null，循环自然结束、返回 null。

要强调的是，这次相遇只证明环存在，相遇点一般并不是环入口——fast 是在环里绕圈追上 slow 的，追上的位置取决于环的形状。把相遇点直接当答案返回，是这道题最常见的错误。

为什么从头和相遇点同速走，会在入口碰头

设链表头到环入口的距离为 a，入口沿环走到相遇点的距离为 b，环长为 c。相遇那一刻 fast 的路程是 slow 的两倍：slow 走了 a+b，fast 走了 a+b 再加若干整圈。把两倍关系展开消项，得到 a 等于 c-b 加上若干整圈。

翻译成白话：从链表头再走 a 步会到达入口；而从相遇点出发走同样的 a 步，等于先补完这一圈剩下的 c-b 步回到入口、再原地绕几个整圈，落点还是入口。所以让一个新指针从头出发、slow 留在相遇点，两者同速各走一步，第一次相遇必然发生在环入口，返回那个节点即可。

复杂度与三个容易写错的地方

阶段一最多走 O(n) 步就会相遇或出局，阶段二再走头到入口的距离，总时间 O(n)；始终只用两三个指针，空间 O(1)。

易错点：一是循环条件必须同时判 fast 和 fast.next 非空，fast 一次跨两步，少判一个就会空指针崩溃；二是把相遇点当环入口直接返回，跳过了整个阶段二；三是阶段二的两个指针必须严格同速各走一步，上面的数学推导建立在同速之上，速度不一致就永远不会在入口相遇。

Python

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # 慢走 1 步
        fast = fast.next.next        # 快走 2 步
        if slow is fast:            # 阶段① 相遇
            p = head
            while p is not slow:    # 阶段② 头与相遇点同速走
                p = p.next
                slow = slow.next
            return p                # 再相遇 = 环入口
    return None                     # fast 到 null = 无环

C++

ListNode* detectCycle(ListNode* head){
    ListNode *slow = head, *fast = head;
    while(fast && fast->next){
        slow = slow->next;          // 慢 1 步
        fast = fast->next->next;    // 快 2 步
        if(slow == fast){           // 阶段① 相遇
            ListNode* p = head;
            while(p != slow){       // 阶段② 同速走
                p = p->next;
                slow = slow->next;
            }
            return p;               // 环入口
        }
    }
    return nullptr;                 // 无环
}

Java

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;            // 慢 1 步
        fast = fast.next.next;       // 快 2 步
        if (slow == fast) {          // 阶段① 相遇
            ListNode p = head;
            while (p != slow) {      // 阶段② 同速走
                p = p.next;
                slow = slow.next;
            }
            return p;                // 环入口
        }
    }
    return null;                     // 无环
}