Problem Statement
Given the head of a linked list, return the node where the cycle begins.
If there is no cycle, return null.
You are not allowed to modify the linked list.
Example
Input:
3 -> 2 -> 0 -> -4
^ |
|_________|
Output:
Node with value 2
Brute Force Approach
Intuition
For every node visited, store its reference in a HashSet.
If we encounter a node that already exists in the HashSet, that node is the starting point of the cycle.
Interview Explanation
Since a cycle means revisiting the same node again, I can maintain a HashSet of visited node references. While traversing the list, if a node is already present in the set, it indicates that we've reached the cycle entry point.
Java Code
public ListNode detectCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
while (head != null) {
if (visited.contains(head)) {
return head;
}
visited.add(head);
head = head.next;
}
return null;
}
Complexity Analysis
| Complexity | Value |
|---|---|
| Time | O(N) |
| Space | O(N) |
Why Optimize?
The HashSet solution works well but requires extra memory.
The interviewer usually asks:
Can you solve it using constant extra space?
This leads us to Floyd's Cycle Detection Algorithm, one of the most important Linked List techniques.
Optimal Approach
Key Observation
If a cycle exists:
- Slow pointer moves one step.
- Fast pointer moves two steps.
Eventually, both pointers must meet inside the cycle.
Once they meet:
- Move one pointer back to the head.
- Keep the other pointer at the meeting point.
- Move both one step at a time.
- The point where they meet again is the start of the cycle.
Why Does This Work?
Assume:
L = Distance from head to cycle start
C = Distance from cycle start to meeting point
R = Remaining cycle length
At meeting point:
Distance travelled by Slow = L + C
Distance travelled by Fast = L + C + n(C + R)
Since Fast travels twice as much:
2(L + C) = L + C + n(C + R)
L + C = n(C + R)
L = n(C + R) - C
Which means:
L = (n - 1)(C + R) + R
So when:
- One pointer starts from Head
- One pointer starts from Meeting Point
Both moving one step at a time,
they will meet exactly at the cycle entry node.
Algorithm
Step 1
Use Slow and Fast pointers to detect whether a cycle exists.
Step 2
If Slow and Fast meet:
- Move Slow back to Head.
- Keep Fast at meeting point.
Step 3
Move both one step at a time.
Step 4
The node where they meet is the cycle starting node.
Optimal Java Solution
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
// Detect cycle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Find cycle entry
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
Dry Run
Input
3 -> 2 -> 0 -> -4
^ |
|_________|
Cycle starts at node 2.
Step 1: Detect Cycle
slow = 3
fast = 3
Iteration 1
slow = 2
fast = 0
Iteration 2
slow = 0
fast = 2
Iteration 3
slow = -4
fast = -4
Pointers meet.
Step 2: Move Slow to Head
slow = 3
fast = -4
Move both one step:
slow = 2
fast = 2
They meet again.
Answer
Cycle starts at node 2
Complexity Analysis
| Operation | Complexity |
|---|---|
| Cycle Detection | O(N) |
| Find Entry Point | O(N) |
Total Time Complexity
O(N)
Space Complexity
O(1)
Pattern Recognition
Whenever you hear:
Cycle Detection
Cycle Entry Point
Loop in Linked List
Think:
Floyd's Tortoise and Hare Algorithm
Slow = 1 Step
Fast = 2 Steps
This pattern is used in:
- Linked List Cycle
- Linked List Cycle II
- Happy Number
- Duplicate Number Detection
- Circular Array Problems
Interview One-Liner
I use Floyd's Cycle Detection Algorithm to first identify a meeting point inside the cycle and then reset one pointer to the head. Moving both pointers one step at a time guarantees that they meet at the cycle's entry node, achieving O(N) time and O(1) space.
Top comments (0)