Description
Determine whether following next pointers eventually revisits a node. Examples supply values and the zero-based tail connection position, or -1 for no cycle; position is not a method argument.
Solution
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return FalseExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,2,3],0]- Output
true
The tail points to the node at index zero.
Example 2
- Input
[[1],-1]- Output
false
The sole node points to null.
Example 3
- Input
[[1],0]- Output
true
The node points back to itself.
Approach
Move a slow pointer one step and a fast pointer two steps; a cycle forces them to meet.
Time & space
O(n) time; O(1) space. Here n is the input length.