LeetCode #142 Linked List Cycle II

Medium

Problem

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Solution

Use two pointer with different speed, say runner and walker, and make runner be twice faster than walker. If there is no cycle in this linked list, runner will finally run through entire list without meet walker.

If there exists a cycle, they will meet each other at a node, say x, and x represents the x-th node in this list. Let’s assume the position of cycle start is at y-th node and the length of cycle is m.

1. About runner, it has already run 2x nodes, which is equal to y + m + (x — y) (length to cycle start + length of cycle + nodes to meet walker). So we have 2x = y + m + (x — y), and it can conduct to x = m.
2. About walker, it needs to walk more m — (x — y) = m — x + y nodes to reach cycle start. As we know in 1 that x is equal to m, walker needs to walk more y nodes to reach the node of cycle start.

By 1 and 2, we can put another pointer, say seeker, with the same speed as walker at the head. Because seeker also needs y move nodes to reach the node of cycle start, the node that seeker and walker meet each other will be what we are looking for.

Complexity

Let n denotes to count of all nodes in this linked list, x denotes to the x-th node is the node that runner meets walker and y denotes to the node that cycle starts.

1. If there is no cycle in this linked list, it takes O(n/2) time for runner to go through entire list.
2. If there exists a cycle in linked list, runner needs to take O(x) time to meet walker. And after they meet each other, it takes O(y) time to let seeker meet walker. So it will take O(x+y) = O(n+n) = O(n) time because x and y are both less than n.

By 1 and 2, it’s clear that it takes O(n/2 + n) = O(n) time for detecting node of cycle start.

For space complexity, it only uses O(1) extra space.