The problem
Given the head of a linked list, return true if it has a cycle — some node whose next arrows, followed along, eventually lead back to it — and false if the list ends.
Here the input is the values and pos, the position the last node’s arrow points back to (−1 for none). The code only ever receives head.
Examples
- Input
head = [3, 2, 0, -4], pos = 1
- Output
true
- Input
head = [1, 2], pos = 0
- Output
true
- Input
head = [1], pos = -1
- Output
false
Constraints
- 0 ≤ number of nodes ≤ 10⁴
- −10⁵ ≤ Node.val ≤ 10⁵
posis −1 or a valid position.
The idea
A set of visited nodes would find the repeat, but costs memory. Floyd’s tortoise and hare uses none: slow moves one node a step, fast two.
If the list ends, fast reaches the end first: no cycle. If there is a cycle, both end up going round it, and each step fast gains exactly one node on slow — so the gap shrinks by one every step and it must reach zero: they meet.
- Time
- O(n) — they meet within one lap of the cycle
- Space
- O(1)
Solution · every language run against every case
class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = fast = head while fast and fast.next: slow = slow.next # one step fast = fast.next.next # two steps if slow is fast: # in a loop, the fast one laps the slow one return True return False # the fast one fell off the end: no loop