Linked List Cycle II
Problem Statement
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
The input may describe pos, the index where the tail connects back, but pos is not passed to the function. You must identify the entrance using pointers only.
Input
The head pointer of a singly linked list that may or may not contain a cycle.
Output
The node where the cycle begins, or null when the list has no cycle.
Constraints
- •
The number of nodes is in the range 0 to 10^4 - •
-10^5 <= Node.val <= 10^5 - •
pos is -1 or a valid node index in the list - •
Do not modify the linked list
Examples
Example 1
head = [3,2,0,-4], pos = 1
node with value 2Example 2
head = [1,2], pos = 0
node with value 1Example 3
head = [1], pos = -1
nullLearning Objectives
- Use Floyd's first meeting point to prove a cycle exists.
- Derive why resetting one pointer to head finds the cycle entrance.
- Move both pointers one step at a time after the meeting point.
- Return null cleanly when the detection phase reaches the tail.
Intuition
Pattern Recognition
This is the same fast and slow signal as cycle detection, but the ask is stronger: find the first repeated node, not just whether repetition exists. The important clue is that once slow and fast meet inside the cycle, the meeting point carries enough distance information to locate the entrance.
The pointer trap is stopping too early. The meeting node is not necessarily the entrance. After the catch, reset one pointer to head, keep the other at the meeting node, and move both one step at a time. Their next meeting is exactly the cycle entry.
Common mistakes
- ×Returning the first meeting node even though it may be deeper inside the cycle.
- ×Resetting both pointers to head, which loses the useful meeting position.
- ×Moving one pointer two steps during the second phase instead of moving both one step.
- ×Forgetting to return **null** when the first phase reaches the end of an acyclic list.
Algorithm Explanation
Key idea
First use Floyd's tortoise and hare to get any meeting point inside the cycle. Then place one pointer at head and leave the other at the meeting point. Moving both one step at a time makes them meet at the entrance.
Pointer walkthrough
For 3 -> 2 -> 0 -> -4 -> 2 ..., Floyd's first phase can meet at -4. Now put finder at 3 and keep slow at -4. Move both one step: finder goes to 2, and slow follows the cycle from -4 to 2. They meet at 2, the cycle entrance.
The informal proof is distance based. Let a be the distance from head to entry, b the distance from entry to the meeting point, and c the cycle length. At the first meeting, fast has traveled exactly one or more full cycles more than slow, so a + b is a multiple of c. Therefore a equals c - b modulo the cycle length. In words, the head-to-entry distance is the same as the meeting-to-entry distance modulo the cycle length. That is why resetting one pointer to head and advancing both by one lands them together at the entry.
Algorithm
- Start slow = head and fast = head.
- Move slow one step and fast two steps while both fast moves are safe.
- If slow == fast, a cycle exists; stop the detection phase.
- If the loop ends because fast reaches null, return null.
- Set finder = head while slow stays at the meeting node.
- Move finder and slow one step at a time until they meet.
- Return the meeting node as the cycle entrance.
Solutions
Solution: Floyd entry-point reset
The first phase detects a cycle and captures a meeting node. The second phase uses the distance relationship between head, entry, and meeting: one pointer starts at head, the other at the meeting node, and equal-speed movement converges at the entrance.
Step-by-step
- Run the normal Floyd loop with slow and fast.
- If fast reaches null, return null because the list is acyclic.
- When slow and fast meet, initialise finder at head.
- Move finder and slow one node per iteration.
- Return the node where they meet; it is the cycle entrance.
O(n)
O(1)
Detection and entry search each take at most linear pointer moves with no extra data structure.
Java implementation
Dry Run
Sample input
head = 3 -> 2 -> 0 -> -4, with the tail pointing back to 2.
| phase | slow | fast or finder | action | meaning |
|---|---|---|---|---|
| detect start | 3 | 3 | both begin at head | no cycle proof yet |
| detect move 1 | 2 | 0 | slow moves one, fast moves two | not equal |
| detect move 2 | 0 | 2 | fast wraps through the cycle | not equal |
| detect move 3 | -4 | -4 | pointers meet | cycle confirmed |
| entry move 0 | -4 | 3 | finder resets to head | prepare equal-speed walk |
| entry move 1 | 2 | 2 | both move one step | entry found |
The first meeting at -4 proves a cycle. The reset phase then meets at 2, so the returned node is the entrance.
Interview Tips
Do not hand-wave the reset step. A concise proof using a, b, and cycle length c is often what separates a memorized solution from an interview-ready explanation. Also clarify that the list is not modified and that the node reference, not the value, is returned.
Likely follow-ups
- How would you compute the length of the cycle after finding the entrance?
- How would you remove the cycle safely once the entrance is known?
- Can you solve the problem with a hash set, and what space tradeoff does it make?
- How does this reset idea appear in Find the Duplicate Number?
Similar Problems
Key Takeaways
- The first Floyd meeting is proof of a cycle, not necessarily the cycle entrance.
- After a meeting, head-to-entry distance equals meeting-to-entry distance modulo the cycle length.
- Reset one pointer to head and move both one step to find the entrance.
- Return **null** when the detection phase reaches the list end.