Linked List Cycle
- 2 min read
- LC-Easy
- Linked List
3 years ago
Solution
- A naive solution is to use a hashmap and store the actual nodes inside. Whenever a duplicate is seen, return True. But this uses O(n) space. We can do it with constant space.
- Solved using Floyd's Tortoise and Hare
- Initialize slow and fast at head.
- Move fast twice, slow one by one
- If there's a cycle, both will meet at same node at same point
- If not, fast will become null
- How is it guaranteed that both will meet at some point?
- In a single iteration of the loop, the distance between the slow and fast pointers is being closed by 1
-
Take the pic below. Let's say the distance between slow and fast is 10.
- Slow moves one node ahead. Total distance between them is now 10 + 1 = 11
- Fast moves two nodes ahead. Total distance between them is now 11 - 2 = 9
- We started out with the pointers being 10 nodes apart, and it decreased to 9
- The distance is being closed by 1 node each time- this means they will eventually meet.
-
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False