Linked List Cycle
You get the head of a singly linked list. A cycle exists if some node can be reached again by following next pointers from itself, which means the walk never reaches the end.
In the tests, the list is described by its values and a position pos: the last node's next pointer points back to the node at index pos (counting from 0), and pos = -1 means the last node points to nothing. The position is only used to build the list; your function receives just the head.
Return true if the list has a cycle, and false otherwise.
Examples
The curved arrow shows where the last node points back to.
Input values = [3, 2, 0, -4], pos = 1
Output true
The last node points back to the node holding 2.
The curved arrow shows where the last node points back to.
Input values = [1, 2], pos = 0
Output true
The last node points back to the head.
Input values = [1], pos = -1
Output false
Constraints
- 0 <= number of nodes <= 10,000
- -100,000 <= node value <= 100,000
- pos is -1 or a valid index of the list
Stuck? Take one hint at a time
Common mistakes
- Comparing node values instead of the nodes themselves, which reports a cycle in a list with repeated values.
- Moving the fast pointer without checking fast.next first, which crashes on the last node (odd length) or past the end (even length).
- Checking slow == fast before the first move while both start at the head, which reports a cycle for every non-empty list.
- Checking only the head for a link back to itself, which misses cycles that begin later.
Questions an interviewer may ask next
- Find the node where the cycle begins. (After the runners meet, restart one from the head and move both one step at a time.)
- Find the length of the cycle. (Walk once round from the meeting point.)
- Why does the fast pointer move by two and not three? What changes if it moves by three? (It still works, but the argument needs more care.)
- Detect a cycle in a sequence of numbers generated by a function. (The same idea, applied to Happy Number or Find the Duplicate Number.)
head
{"values":[3,2,0,-4],"pos":1}Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.