#141
Linked List Cycle
Easy Floyd's cycle detection
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a linked list has a cycle (some node's next points back to an earlier node).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does the list loop back on itself?
Why this works: on a circular track a faster runner always laps a slower one; on a straight road the fast one reaches the end.
Example: 3 → 2 → 0 → -4 → (back to 2)
slow 2, fast 0 → slow 0, fast 2 → slow -4, fast -4 → meet → cycle✦Hints open one at a time
A HashSet of visited nodes works but uses O(n) space.
Two runners on a circular track: the faster one eventually laps the slower one.
↗Approach
Move slow one step and fast two steps. If they ever meet, there's a cycle; if fast reaches null, there isn't.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // compare after moving
}
return false;
}
}!Common mistake
Checking slow == fast before moving them — they start equal, so you'd always say "cycle".
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon