Linked List Cycle
EasyFloyd's tortoise & hare
Send a slow walker and a fast runner; if they ever meet, the path loops in a circle.
The idea
Move one pointer one step and another two steps. If there's a loop, the fast pointer laps the slow one and they meet; if it ever hits null, there's no cycle.
slow
fast
3
2
0
-4
Step 1 of 5. Slow moves one step, fast moves two. In a loop the fast pointer eventually laps the slow one.
1/5
Optimal
timeO(n)spaceO(1)
They meet iff a cycle exists.
1let slow = head, fast = head;2while (fast && fast.next) {3 slow = slow.next;4 fast = fast.next.next;5 if (slow === fast) return true;6}7return false;Input
- list
- [3, 2, 0, -4]
Memory
- slow
- = 0
- fast
- = 0
Output
- cycle
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 2 -> 3 -> 4 -> (back to 2)
- Output:
- true
- Explanation:
- The tail loops back, so a cycle exists.
Example 2
- Input:
- list = 1 -> 2 -> 3
- Output:
- false
- Explanation:
- It ends normally with no loop.
Example 3
- Input:
- list = 1 -> (back to 1)
- Output:
- true
- Explanation:
- A node pointing to itself is a cycle.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.