Linked List Cycle II
Problem
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
- The number of nodes in the list is in the range [0, 10⁴]
- −10⁵ ≤ Node.val ≤ 10⁵
- pos is −1 or a valid index in the linked-list
Example
head = [3,2,0,-4], where the tail connects to the node at position 1 (0-indexed)Reference to the node with value 2The algorithm uses two pointers moving at different speeds to detect a cycle. Initially, both pointers start at the head. The fast pointer moves two steps at a time, while the slow pointer moves one step. If a cycle exists, the two pointers will eventually meet inside the cycle. Once they meet, resetting one pointer to the head and moving both one step at a time leads them to meet again at the cycle's start node. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start along the cycle.
Approach
Straightforward Solution
A brute-force approach uses a hash set to track visited nodes, returning the first repeated node. This requires O(n) extra space and is less optimal.
Core Observation
If a cycle exists, two pointers moving at different speeds will eventually meet inside the cycle due to the relative speed difference.
Path to Optimal
The key insight is Floyd's Tortoise and Hare algorithm: use two pointers moving at different speeds to detect a cycle without extra space. After detecting a cycle, resetting one pointer to the head and moving both pointers at the same speed leads to their meeting point being the cycle's start node. This works because the distance from head to cycle start equals the distance from meeting point to cycle start along the cycle.
Optimal Approach
Use two pointers, slow and fast, starting at head. Move slow by one step and fast by two steps until they meet or fast reaches the end (no cycle). If they meet, reset slow to head and move both pointers one step at a time until they meet again; this node is the cycle start. Return this node. If no cycle, return null.
Time
O(n)
Each pointer traverses the list at most a constant number of times. The fast pointer moves twice as fast, so the detection phase is O(n), and the entry point search is also O(n).
Space
O(1)
Only two pointers are used, with no additional data structures, resulting in constant auxiliary space.
Pattern Spotlight
Fast & Slow Pointers (Cycle Detection and Entry Point Identification)
When detecting cycles in linked structures, use two pointers moving at different speeds to find a meeting point inside the cycle; then reset one pointer to the start and move both at equal speed to find the cycle's entry point.
Solution
| 1 | class Solution: |
| 2 | def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: |
| 3 | |
| 4 | slow = head |
| 5 | fast = head |
| 6 | |
| 7 | while fast and fast.next: |
| 8 | |
| 9 | slow = slow.next |
| 10 | fast = fast.next.next |
| 11 | |
| 12 | if slow == fast: |
| 13 | slow = head |
| 14 | |
| 15 | while slow != fast: |
| 16 | slow = slow.next |
| 17 | fast = fast.next |
| 18 | |
| 19 | return slow |
| 20 | |
| 21 | return None |
Step-by-Step Solution
Initialize Slow and Fast Pointers at Head
| 4 | slow = head |
| 5 | fast = head |
Objective
To set up two pointers that will traverse the linked list at different speeds to detect a cycle.
Key Insight
Starting both pointers at the head ensures they begin traversal from the same position. The fast pointer moves twice as fast as the slow pointer, which guarantees that if a cycle exists, they will eventually meet inside the cycle. This setup is the foundation of Floyd's cycle detection algorithm.
Interview Quick-Check
Core Logic
Both pointers start at the head to ensure synchronized traversal and correct detection of cycles.
Common Pitfalls & Bugs
Initializing pointers incorrectly (e.g., fast starting at head.next) can cause missed cycles or incorrect detection.
Traverse List to Detect Cycle via Pointer Meeting
| 7 | while fast and fast.next: |
| 9 | slow = slow.next |
| 10 | fast = fast.next.next |
Objective
To move the slow pointer by one step and the fast pointer by two steps until they meet or the list ends.
Key Insight
The fast pointer moves at double speed, so if a cycle exists, it will lap the slow pointer and meet it inside the cycle. The loop condition ensures traversal stops if the fast pointer reaches the end, indicating no cycle. This phase detects the presence of a cycle without extra space.
Interview Quick-Check
Core Logic
Moving pointers at different speeds guarantees detection of a cycle if one exists.
State & Boundaries
The loop continues only while fast and fast.next are valid to avoid null pointer exceptions.
Common Pitfalls & Bugs
Failing to check fast.next can cause runtime errors.
Identify Cycle Start by Resetting Slow and Moving Both Pointers
| 12 | if slow == fast: |
| 13 | slow = head |
| 15 | while slow != fast: |
| 16 | slow = slow.next |
| 17 | fast = fast.next |
Objective
To find the node where the cycle begins by resetting slow to head and moving both pointers one step at a time until they meet.
Key Insight
After detecting a cycle, resetting slow to head and moving both pointers at the same speed leverages the mathematical relationship between distances traveled. Their meeting point is the cycle's entry node. This step transforms the detection phase into precise identification of the cycle start without extra space or modifications.
Interview Quick-Check
Core Logic
Resetting slow to head and moving both pointers at equal speed exploits the distance equality that leads to the cycle start.
State & Boundaries
The loop continues until slow and fast pointers meet, ensuring the exact cycle start is found.
Common Pitfalls & Bugs
Not resetting slow to head or moving pointers at different speeds here would fail to find the cycle start.
Return the Node Where Cycle Begins or Null if None
| 19 | return slow |
| 21 | return None |
Objective
To return the node where the cycle starts if found, or null if no cycle exists.
Key Insight
Returning the meeting node after the second phase correctly identifies the cycle start. If the fast pointer reaches the end without meeting slow, returning null signals no cycle. This final step cleanly separates detection and identification outcomes.
Interview Quick-Check
Core Logic
Returning slow after the second meeting gives the cycle start node.
State & Boundaries
Returning null when no cycle is detected ensures correct handling of acyclic lists.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if slow == fast:Check if slow and fast pointers have met.
Meeting of slow and fast pointers confirms the presence of a cycle, triggering the next phase to find the cycle's start.
fast = fast.next.nextMove fast pointer two steps forward.
Moving fast two steps ahead ensures it will eventually catch up to slow if a cycle exists, enabling detection without extra space.
slow = headReset slow pointer to the head of the list.
Resetting slow to head prepares for the second phase where both pointers move at the same speed to find the cycle entry point, leveraging the distance equality property.
while slow != fast:Loop until slow and fast pointers meet again.
This loop moves both pointers one step at a time, ensuring they meet at the cycle's start node due to the mathematical relationship between distances traveled.
return slowReturn the node where slow and fast pointers meet (cycle start).
Returning this node correctly identifies the start of the cycle, fulfilling the problem's requirement.
while fast and fast.next:Continue looping while fast and fast.next are not null.
This condition prevents null pointer exceptions and ensures traversal only continues when the fast pointer can safely move two steps ahead.
return NoneReturn null if no cycle is detected.
Returning null signals that the list has no cycle, correctly handling acyclic inputs.
slow = headInitialize the slow pointer to the head of the list.
Starting slow at head ensures it traverses the list at normal speed from the beginning, which is essential for correct cycle detection and later identification of the cycle start.
fast = headInitialize the fast pointer to the head of the list.
Starting fast at head allows it to move twice as fast as slow, enabling the detection of cycles by eventually meeting slow inside the cycle if one exists.
slow = slow.nextMove slow pointer one step forward.
Advancing slow by one step maintains the relative speed difference with fast, which is critical for cycle detection.
slow = slow.nextMove slow pointer one step forward.
Advancing slow by one step synchronizes its pace with fast, enabling convergence at the cycle start.
fast = fast.nextMove fast pointer one step forward.
Advancing fast by one step matches slow's speed, ensuring their meeting point is the cycle's entry node.
Test Your Understanding
Why does resetting one pointer to the head and moving both pointers at the same speed lead to the cycle's start node?
Because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start along the cycle, moving both pointers at the same speed causes them to meet exactly at the cycle's entry.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Linked List Cycle II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Linked List Cycle II drill