LeetCode #141 Linked List Cycle

Easy

Problem

Given a linked list, determine if it has a cycle in it.

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

Solution

Here we will use two pointers walker and runner for detecting cycle. Make runner run two nodes in a iteration and walker go only one node. By doing so, they will finally meet if there is a cycle in this linked list.

Complexity

There are two cases for analytics:

1. If there is no cycle in this linked list, it’s obvious that runner will take O(n/2) time to run through this linked list which n denotes to amount of nodes in this linked list.
2. If there exists a cycle in this linked list, 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. We know after they meet each other, runner 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. Therefore, we know runner has to run O(m) time for catching up walker totally.

Because n is the counts of nodes in linked and m is only the length of cycle, m will definitely be less than n. Therefore, the time complexity will be O(n).

It’s trivial that space complexity of this approach is only O(1).