LeetCode 142: Linked List Cycle II (Floyd + Entry Reset Proof)
LeetCode 142Linked ListTwo PointersToday we solve LeetCode 142 - Linked List Cycle II.
Source: https://leetcode.com/problems/linked-list-cycle-ii/
English
Problem Summary
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. You must not modify the linked list.
Key Insight
Use Floyd's fast/slow pointers. If they meet, a cycle exists. Then move one pointer to head and keep the other at meeting point; both move one step each time. Their next meeting point is exactly the cycle entry.
Why Entry Reset Works
Let distance from head to cycle entry be a, from entry to meeting point be b, and cycle length be L. At meeting time: 2(a+b)=a+b+kL, so a+b=kL, hence a = kL-b. Starting one pointer at head (distance a to entry) and one at meeting point (distance L-b to entry modulo cycle) makes them meet at entry.
Algorithm (Step-by-Step)
1) Initialize slow=head, fast=head.
2) Move slow by 1 and fast by 2 until fast ends (no cycle) or they meet.
3) If no meet, return null.
4) Set p1=head, p2=slow.
5) Move both by 1; first node where p1==p2 is the cycle entry.
Complexity Analysis
Time: O(n).
Space: O(1).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p1 = head;
ListNode p2 = slow;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
}
}func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
p1, p2 := head, slow
for p1 != p2 {
p1 = p1.Next
p2 = p2.Next
}
return p1
}
}
return nil
}class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* p1 = head;
ListNode* p2 = slow;
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
}
return nullptr;
}
};class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p1, p2 = head, slow
while p1 is not p2:
p1 = p1.next
p2 = p2.next
return p1
return Nonevar detectCycle = function(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let p1 = head, p2 = slow;
while (p1 !== p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
};中文
题目概述
给定链表头节点，返回环的入口节点；如果无环，返回 null。要求不修改链表结构。
核心思路
先用 Floyd 快慢指针判断是否有环：慢指针每次一步，快指针每次两步。若相遇说明有环。然后把一个指针移回头结点，另一个留在相遇点，两者都每次走一步，再次相遇的位置就是环入口。
为什么“回头重走”一定到入口
设头到入口距离为 a，入口到相遇点距离为 b，环长为 L。相遇时满足：2(a+b)=a+b+kL，可得 a+b=kL，即 a=kL-b。所以从头走 a 步到入口；从相遇点走 kL-b 步也正好到入口（环上等价于走 L-b）。因此两指针会在入口相遇。
算法步骤
1）初始化 slow=head，fast=head。
2）循环：slow 走一步，fast 走两步。若 fast 到尾部则无环。
3）若相遇，说明有环。
4）设 p1=head，p2=slow（相遇点）。
5）两者同步每次一步，再次相遇点即环入口。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p1 = head;
ListNode p2 = slow;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
}
}func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
p1, p2 := head, slow
for p1 != p2 {
p1 = p1.Next
p2 = p2.Next
}
return p1
}
}
return nil
}class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* p1 = head;
ListNode* p2 = slow;
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
}
return nullptr;
}
};class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p1, p2 = head, slow
while p1 is not p2:
p1 = p1.next
p2 = p2.next
return p1
return Nonevar detectCycle = function(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let p1 = head, p2 = slow;
while (p1 !== p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
};
Comments