71. Linked List Cycle
🔗 LeetCode Problem: 141. Linked List Cycle
📊 Difficulty: Easy
🏷️ Topics: Linked List, Hash Table, Two Pointers
Problem Statement
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Visual:
3 -> 2 -> 0 -> -4
↑ ↓
└──────────┘
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Visual:
1 -> 2
↑ ↓
└────┘
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Visual:
1 -> null
Constraints:
- The number of the nodes in the list is in the range [0, 10^4].
- -10^5 <= Node.val <= 10^5
- pos is -1 or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
🎨 Visual Understanding
The Problem Visualized
Example 1: Cycle exists
List: 3 -> 2 -> 0 -> -4
↑ ↓
└──────────┘
Starting from 3:
3 -> 2 -> 0 -> -4 -> 2 -> 0 -> -4 -> 2 -> ...
(back to 2, infinite loop!)
The tail (-4) points back to node 2
This creates a CYCLE!
Example 2: No cycle
List: 3 -> 2 -> 0 -> -4 -> null
Starting from 3:
3 -> 2 -> 0 -> -4 -> null (end reached, no cycle)
The tail points to null
No cycle!
How to detect a cycle?
Imagine two people running on a circular track:
- One runs at 1x speed (slow)
- One runs at 2x speed (fast)
If the track is circular:
The faster runner will eventually LAP the slower one
They WILL meet at some point!
If the track is straight:
The faster runner reaches the end
They NEVER meet!
Same logic for linked lists!
🚨 CRITICAL INSIGHT - Floyd's Cycle Detection!
The Key Pattern!
Use two pointers moving at different speeds:
- Slow pointer: moves 1 step at a time
- Fast pointer: moves 2 steps at a time
If there's a cycle:
Fast will eventually catch up to slow
They MUST meet inside the cycle!
If there's no cycle:
Fast will reach the end (null)
Loop terminates
This is Floyd's Cycle Detection Algorithm!
Also called "Tortoise and Hare" algorithm 🐢🐇
Why Two Speeds Guarantee Meeting
Mathematical proof:
If there's a cycle of length C:
Once both pointers are in the cycle,
their distance closes by 1 each step.
Example: Cycle length = 5
Initially:
Slow at position 0 in cycle
Fast at position 3 in cycle
Distance = 3
After 1 iteration:
Slow at position 1 (moved 1)
Fast at position 0 (moved 2, wrapped around)
Distance = 4 (or -1, which is 4 in cycle)
After 2 iterations:
Slow at position 2
Fast at position 2
They meet! ✓
The distance decreases by 1 each iteration:
3 -> 2 -> 1 -> 0 (meet!)
They ALWAYS meet within C iterations
after both enter the cycle!
Visual Trace
List: 1 -> 2 -> 3 -> 4 -> 5
↑ ↓
└─────────┘
Initial:
slow = 1
fast = 1
Step 1:
slow = 2 (moved 1 step)
fast = 3 (moved 2 steps)
Step 2:
slow = 3
fast = 5
Step 3:
slow = 4
fast = 3 (wrapped around: 5 -> 3)
Step 4:
slow = 5
fast = 5 (wrapped: 3 -> 5)
slow == fast → Cycle detected! ✓
🎯 Approach 1: Hash Set (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Store visited nodes in a HashSet
If we see a node again, there's a cycle!
Implementation
/**
* Using HashSet to track visited nodes
* Time: O(n), Space: O(n)
*/
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode current = head;
while (current != null) {
// Have we seen this node before?
if (visited.contains(current)) {
return true; // Cycle detected!
}
// Mark as visited
visited.add(current);
current = current.next;
}
return false; // Reached end, no cycle
}
⏰ Time: O(n) - Visit each node once
💾 Space: O(n) - Store all nodes in HashSet
❌ Problem: Uses O(n) space! Not optimal for follow-up!
🎯 Approach 2: Floyd's Cycle Detection (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Use two pointers at different speeds!
If there's a cycle:
Fast pointer will lap slow pointer
They must meet!
If no cycle:
Fast pointer reaches null
Loop ends!
The Strategy:
Floyd's Algorithm (Tortoise and Hare):
1. Initialize slow and fast at head
2. Move slow 1 step, fast 2 steps
3. If they meet → cycle exists
4. If fast reaches null → no cycle
Time: O(n)
Space: O(1) ✓ Solves the follow-up!
Implementation
/**
* Floyd's Cycle Detection Algorithm (Tortoise and Hare)
* Time: O(n), Space: O(1)
*/
public boolean hasCycle(ListNode head) {
// Edge case: empty list or single node
if (head == null || head.next == null) {
return false;
}
// Initialize two pointers
ListNode slow = head; // Tortoise 🐢
ListNode fast = head; // Hare 🐇
// Move pointers until fast reaches end or they meet
while (fast != null && fast.next != null) {
slow = slow.next; // Move 1 step
fast = fast.next.next; // Move 2 steps
// Did they meet?
if (slow == fast) {
return true; // Cycle detected! ✓
}
}
// Fast reached the end (null)
return false; // No cycle
}
⏰ Time: O(n) - Each node visited at most twice
💾 Space: O(1) - Only two pointers
🔍 Dry Run
Example 1: List with cycle
List: 3 -> 2 -> 0 -> -4
↑ ↓
└──────────┘
Initial state:
slow = 3
fast = 3
Iteration 1:
slow = slow.next = 2
fast = fast.next.next = 0
Current positions:
slow: 2
fast: 0
slow == fast? No
Iteration 2:
slow = slow.next = 0
fast = fast.next.next = 2 (wrapped around!)
Current positions:
slow: 0
fast: 2
slow == fast? No
Iteration 3:
slow = slow.next = -4
fast = fast.next.next = -4 (2 -> 0 -> -4)
Current positions:
slow: -4
fast: -4
slow == fast? Yes! ✓
Return true (cycle detected!)
Example 2: List without cycle
List: 3 -> 2 -> 0 -> -4 -> null
Initial state:
slow = 3
fast = 3
Iteration 1:
slow = slow.next = 2
fast = fast.next.next = 0
fast != null && fast.next != null? Yes
Iteration 2:
slow = slow.next = 0
fast = fast.next.next = null (-4 -> null -> null)
fast != null? No!
Loop ends
Return false (no cycle)
Example 3: Single node
List: 1 -> null
Check: head.next == null? Yes
Return false immediately
🎯 Why This Works - Deep Dive
The Two-Speed Strategy:
═══════════════════════════════════════════════════════════════
Why different speeds?
If both move at same speed, they'd never meet!
Different speeds create relative motion
Think of it like a clock:
Hour hand moves slower
Minute hand moves faster
They meet periodically!
In a cycle:
Fast gains 1 position on slow each iteration
Eventually, fast catches up to slow
Distance closes by 1 each step
They MUST meet!
Without cycle:
Fast reaches null
No chance to meet
Loop terminates
The Loop Condition:
═══════════════════════════════════════════════════════════════
Why check both fast and fast.next?
while (fast != null && fast.next != null)
Because fast moves TWO steps:
fast = fast.next.next
If we only check fast != null:
fast might be the last node
fast.next is null
fast.next.next throws NullPointerException! ✗
So we need:
fast != null (fast exists)
fast.next != null (can move one step)
Then safe to do fast.next.next ✓
Edge Cases Handled:
═══════════════════════════════════════════════════════════════
Empty list (head = null):
if (head == null) return false; ✓
Single node (head.next = null):
if (head.next == null) return false; ✓
Two nodes, no cycle:
1 -> 2 -> null
slow = 1, fast = 1
Step 1: slow = 2, fast = null
Loop ends, return false ✓
Two nodes, with cycle:
1 -> 2
↑ ↓
└────┘
slow = 1, fast = 1
Step 1: slow = 2, fast = 2
They meet! return true ✓
Time Complexity Proof:
═══════════════════════════════════════════════════════════════
Case 1: No cycle
Fast reaches end after n/2 steps
Time: O(n) ✓
Case 2: With cycle
Phase 1: Enter the cycle
Both pointers take at most n steps
Phase 2: Meet in cycle
Distance between them: at most C (cycle length)
Closes by 1 each step
Takes at most C steps
Total: O(n) + O(C) = O(n) ✓
(C ≤ n, so dominated by n)
Space: O(1)
Only two pointers, no extra data structures! ✓
Why Fast Catches Slow (Mathematical Proof)
Proof: Fast WILL catch slow in a cycle
Assumptions:
- Cycle length = C
- Both pointers in cycle
- Distance between them = d (where 0 < d < C)
Each iteration:
- Slow moves 1 step
- Fast moves 2 steps
- Fast gains 1 position relative to slow
Initial distance: d
After 1 iteration: d - 1
After 2 iterations: d - 2
...
After d iterations: 0 (they meet!)
Since d < C, and distance reduces by 1 each time,
they MUST meet within C iterations! ✓
Example:
C = 6, d = 4
Iteration 0: distance = 4
Iteration 1: distance = 3
Iteration 2: distance = 2
Iteration 3: distance = 1
Iteration 4: distance = 0 → Meet!
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong loop condition
// ❌ WRONG - Can throw NullPointerException
while (fast != null) {
fast = fast.next.next; // What if fast.next is null?
}
// ✓ CORRECT - Check both
while (fast != null && fast.next != null) {
fast = fast.next.next;
}
Mistake 2: Moving pointers in wrong order
// ❌ WRONG - Check before moving!
while (fast != null && fast.next != null) {
if (slow == fast) {
return true; // Checks before moving, always true at start!
}
slow = slow.next;
fast = fast.next.next;
}
// ✓ CORRECT - Move first, then check
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
Mistake 3: Not initializing both at head
// ❌ WRONG - Fast starts ahead
ListNode slow = head;
ListNode fast = head.next;
// ✓ CORRECT - Both start at head
ListNode slow = head;
ListNode fast = head;
Mistake 4: Forgetting edge cases
// ❌ WRONG - No null check
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// What if head is null? NullPointerException!
}
// ✓ CORRECT - Handle edge cases
if (head == null || head.next == null) {
return false;
}
Mistake 5: Using wrong speed
// ❌ WRONG - Both move at same speed
slow = slow.next;
fast = fast.next; // Will never meet in cycle!
// ✓ CORRECT - Different speeds
slow = slow.next; // 1 step
fast = fast.next.next; // 2 steps
🎯 Pattern Recognition
Problem Type: Cycle Detection in Linked List
Core Pattern: Fast & Slow Pointers (Floyd's Algorithm)
When to Apply:
✓ Detect cycle in linked list
✓ Need O(1) space (can't use HashSet)
✓ Can't modify the list
✓ Single pass through list
✓ Two pointer technique applicable
Recognition Keywords:
- "Linked list"
- "Cycle" or "circular"
- "O(1) space" or "constant memory"
- "Without extra space"
- "Detect loop"
Similar Problems:
- Linked List Cycle II (LC 142) - Find cycle start
- Happy Number (LC 202) - Cycle in transformations
- Find Duplicate Number (LC 287) - Array as linked list
Key Components:
┌────────────────────────────────────────────┐
│ 1. Two pointers: slow and fast │
│ 2. Different speeds: 1x and 2x │
│ 3. Meet in cycle or fast reaches null │
│ 4. O(n) time, O(1) space │
└────────────────────────────────────────────┘
This is THE fundamental fast & slow pointers pattern!
🧠 Interview Strategy
Step 1: "Cycle detection → Fast & slow pointers"
Step 2: "Floyd's algorithm: two speeds"
Step 3: "If cycle, they meet; if no cycle, fast reaches null"
Step 4: "O(n) time, O(1) space"
Key Points to Mention:
- Use two pointers at different speeds
- Slow moves 1 step, fast moves 2 steps
- If they meet, cycle exists
- If fast reaches null, no cycle
- Check: fast != null && fast.next != null
- Handle edge cases: null, single node
- Time: O(n), Space: O(1)
- Alternative: HashSet O(n) space
Why This Approach?
"I'll use Floyd's cycle detection algorithm with two pointers
moving at different speeds. The slow pointer moves one step at
a time while the fast pointer moves two steps. If there's a
cycle, the fast pointer will eventually lap the slow pointer
and they'll meet. If there's no cycle, the fast pointer will
reach the end. This gives O(n) time with O(1) space, which
solves the follow-up requirement."
Why Two Different Speeds?
"If both pointers move at the same speed, they'd maintain the
same distance and never meet. By having one move faster, the
gap closes by 1 each iteration. In a cycle, this guarantees
they'll eventually meet."
Edge Cases to Mention:
✓ Empty list (null)
✓ Single node
✓ Two nodes with/without cycle
✓ All nodes in cycle
✓ Cycle at the end
📝 Quick Revision Notes
🎯 Core Concept:
Linked List Cycle: Use Floyd's algorithm 🐢🐇. Two pointers: slow (1 step), fast (2 steps). If cycle: they meet. If no cycle: fast reaches null. Loop: while (fast != null && fast.next != null). O(n) time, O(1) space!
⚡ Quick Implementation:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
class Test {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Test t = new Test();
ListNode head1 = new ListNode(3); // 3,2,0,-4 (-4 -> 2 is a loop)
head1.next = new ListNode(2);
head1.next.next = new ListNode(0);
head1.next.next.next = head1.next;
System.out.println("head1: "+t.hasCycle(head1)); // true
System.out.println("head2: "+t.hasCycle(null)); // empty list // false
System.out.println("head3: "+t.hasCycle(new ListNode(1))); // single element // false
ListNode head4 = new ListNode(1); // 1 - self loop to itself
head4.next = head4;
System.out.println("head4: "+t.hasCycle(head4)); // true
ListNode head5 = new ListNode(3); // 3,2 (no loop)
head5.next = new ListNode(2);
System.out.println("head5: "+t.hasCycle(head5)); // false
ListNode head6 = new ListNode(3); // 3,2,0,-4 (-4 -> 3 is a loop)
head6.next = new ListNode(2);
head6.next.next = new ListNode(0);
head6.next.next.next = new ListNode(-4);
head6.next.next.next.next = head6;
System.out.println("head6: "+t.hasCycle(head6)); // true
ListNode head7 = new ListNode(3); // 3,2,0,-4 (-4 -> 0 is a loop)
head7.next = new ListNode(2);
head7.next.next = new ListNode(0);
head7.next.next.next = new ListNode(-4);
head7.next.next.next.next = head7.next.next.next;
System.out.println("head7: "+t.hasCycle(head7)); // true
}
}
🔑 Key Insights:
- Pattern: Fast & Slow Pointers (Floyd's)
- Slow: Moves 1 step (tortoise 🐢)
- Fast: Moves 2 steps (hare 🐇)
- Cycle: Pointers meet inside cycle
- No Cycle: Fast reaches null
- Loop: Check
fast != null && fast.next != null - Why both checks?: Fast moves 2 steps, need both valid
- Edge: Handle null and single node
- Time: O(n), Space: O(1)
🎪 Memory Aid:
"Tortoise and hare race! If circular track, hare laps tortoise!"
Think: "Two speeds, same starting point, meet if cycle!" 🐢🐇
💡 The Key Insight:
Different speeds create relative motion!
If cycle:
Fast gains 1 position each step
Distance closes: d → d-1 → d-2 → ... → 0
They MUST meet!
If no cycle:
Fast reaches null
Loop ends!
⚠️ Critical Details:
1. Check: fast != null AND fast.next != null
2. Why both? Fast moves 2 steps (fast.next.next)
3. Start: Both at head
4. Move: slow 1 step, fast 2 steps
5. Check: AFTER moving (not before)
6. Meet: slow == fast → return true
7. End: fast reaches null → return false
8. Edge: Handle null and single node first
🔥 The Loop Condition:
while (fast != null && fast.next != null)
└─────┬──────┘ └──────┬──────────┘
│ │
Fast exists Next step valid
If only check fast != null:
fast might be last node
fast.next = null
fast.next.next = NullPointerException! ✗
Check both for safety! ✓
💡 Why They Meet:
Cycle length = C
Initial distance between them = d
Each iteration:
Slow: +1 position
Fast: +2 positions
Gap closes: -1
After d iterations: gap = 0 (they meet!)
Guaranteed within C iterations! ✓
🧪 Edge Cases
Case 1: Empty list
Input: head = null
Output: false
(No nodes, no cycle)
Case 2: Single node, no cycle
Input: head = [1], pos = -1
Output: false
(1 -> null)
Case 3: Single node, self-loop
Input: head = [1], pos = 0
Output: true
(1 -> 1, points to itself)
Case 4: Two nodes, no cycle
Input: head = [1,2], pos = -1
Output: false
(1 -> 2 -> null)
Case 5: Two nodes, cycle
Input: head = [1,2], pos = 0
Output: true
(1 -> 2 -> 1)
Case 6: All nodes in cycle
Input: head = [1,2,3], pos = 0
Output: true
(1 -> 2 -> 3 -> 1)
Case 7: Cycle at end
Input: head = [1,2,3,4], pos = 2
Output: true
(1 -> 2 -> 3 -> 4 -> 3)
All handled correctly! ✓
Related Patterns
- Linked List Cycle II (LC 142) - Find cycle start
- Happy Number (LC 202) - Cycle in number transformations
- Find Duplicate Number (LC 287) - Array as linked list
Happy practicing! 🎯
Note: This is the FOUNDATION of fast & slow pointers! Master this, and you'll ace all related problems! Floyd's algorithm is elegant and powerful! 🐢🐇