LeetCode: 142. Linked List Cycle II

Summary

Return the node where the cycle begins, if there's no cycle in the linked list, return null.

Approach

2 runners approach +


1 -> 2 -> 3 -> 4
          |    |
          6 <- 5

When the slow runner arrived at the node 3, the faster runner is at the node 6 (2*a where a is the slow runner distance * 2).

Then, both nodes meet at the node 4. (slow node 3 -> 4, fast node 6 -> 4).

The position is at minus a position from where the cycle starts (right cycle is the positive).

Then, we start the slow node from the meet location, and another new node from the start of the linked list, They'll meet at the cycle starts.

Function

Initialization:

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

Check if there's a cycle:

Until runner1 is not None and runner2 is not None and runner2.next is not None:

runner1 -> go next
runner2 -> go next next if runner1 is equals to the runner2: mode node is the current runner, and break

if runner1 or runner2: return False (runner1 or runner2 reached to the tail, no cycle in it).

Find where the cycle starts:

Untile runner1 != head: runner1 -> go next head -> go next

return head

Complexity

Time Complexity: O(N) where N is the size of the linked list. Each runner traverse the nodes almost N (in the cycle, slower runner runs 1 cycle, faster runner runs 2 cycles to meet each other. It's constant). Space Complexity: O(1).