Linked List Cycle
Easy· fast and slow pointers
Problem
Given the head of a linked list, decide whether following next pointers ever brings you back to a node you already visited. Return true if there is a cycle and false if the list ends. Try to use constant extra memory.
Examples
Input: head = [3,2,0,-4], tail connects to index 1
Output: true
The last node links back to the node with value 2.
Input: head = [1], no cycle
Output: false
Constraints
- • 0 <= number of nodes <= 10^4
- • pos is -1 or a valid index
Hints & approach
Hint 1
A hash set of visited nodes works, but uses O(n) memory.
Hint 2
Move two pointers at different speeds through the list.
Hint 3
If there is a loop, the faster one must eventually land on the slower one.
Approachtry the hints first
Use Floyd's tortoise and hare: slow moves one step and fast moves two steps per iteration. If fast (or fast.next) hits null, the list terminates and there is no cycle. Inside a cycle the gap between them shrinks by one each step, so they are guaranteed to meet; when slow == fast, return true. Only two pointers are needed.
Time O(n) · Space O(1)