#142
Linked List Cycle II
Medium Floyd's cycle entrance
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the node where a linked list's cycle begins, or null if there is no cycle.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: where does the cycle start?
Why this works: after slow and fast meet, the distance from head to the entrance equals the distance from the meeting point to the entrance. Walk both at speed 1.
Example: 3 → 2 → 0 → -4 → (2)
meet at -4one pointer from 3, one from -4: next steps land on 2 together → entrance 2
✦Hints open one at a time
First detect the meeting point with slow and fast pointers.
Distance from head to the cycle start equals distance from the meeting point to the cycle start (going forward).
↗Approach
After slow and fast meet, start a pointer at head and move it and slow one step at a time; they meet at the cycle entrance.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
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 p = head;
while (p != slow) { // walk both to the entrance
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
}!Common mistake
Returning the meeting point itself — it's somewhere inside the cycle, not necessarily the start.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon