LeetCode: 141. Linked List Cycle

Summary

Determine if the linked list has a cycle in it.

Approach

2 runners approach.

If we use the two runners traverse the linked list with different speeds, the two runners meet at some point if the linked list has a cycle.

Function

Initialization:

runner1: set the current head.
runner2: set the current head.

Until runner1 is not None and runner2 is not None and runner2.next is not None: go runner1 -> runner1.next go runner2 -> runner2.next.next Check if runner1 is equal to runner2, return True.

Return False.

Complexity

Time Complexity: O(N) where N is the size of the linked list. Space Complexity: O(1)