141. Linked List Cycle
The strategy is to use two pointers, a walker and a runner (slow and fast). The walker (slow) moves forward one node at a time. The runner (fast) moves ahead 2 nodes at a time. So if there is a cycle, the runner will eventually lap the walker and the walker and runner will be at the same node. Otherwise the runner will reach the end of the linked list first.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
walker = head
runner = head
while runner and runner.next:
walker = walker.next
runner = runner.next.next
if walker == runner:
return True
return False
Time Complexity: O(N).
Space complexity O(1)
Last modified 1yr ago