Given the head of a linked list, return true if the list contains a cycle, meaning some node can be reached again by following next pointers. In the tests, pos is the index of the node the tail links back to (-1 means no cycle); pos is only used to build the list and is not passed to your function.
- The list has 0 to 10^4 nodes
- -10^5 <= Node.val <= 10^5
- `pos` is -1 or a valid index
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The straightforward method keeps a set of visited nodes and reports a cycle when a node shows up twice: O(n) time and O(n) space. Floyd's tortoise and hare removes the extra memory. A slow pointer moves one step and a fast pointer two steps. Without a cycle, the fast pointer simply falls off the end. With a cycle, once both pointers are inside it, the gap between them shrinks by one each step, so they must meet within one lap.
Algorithm
- Set
slow = headandfast = head. - While
fastandfast.nextare not null: moveslowone step andfasttwo steps. - If
slow == fast(same node, not just same value), return true. - If the loop ends, return false.
O(n)Space: O(1)class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = fast = head while fast and fast.next: slow = slow.next # 1 step fast = fast.next.next # 2 steps if slow is fast: return True # same node: there is a loop return False # fast fell off the end