Why this is a Fast and Slow Pointers problem

Two pointers at different speeds, meeting inside the loop, is the cycle detection variant.

The closest alternative. A hash set is not wrong. It runs in O(N) time and answers the question. It also costs O(N) memory. On a list of 10,000 nodes that is 10,000 stored references.

Two pointers reach the same answer in O(1) space. This pattern is the improvement to offer when you are asked to reduce the memory.

Solution

Imagine two racers running in a circular racing track. If one racer is faster than the other, the faster racer is bound to catch up and cross the slower racer from behind. We can use this fact to devise an algorithm to determine if a LinkedList has a cycle in it or not.

Imagine we have a slow and a fast pointer to traverse the LinkedList. In each iteration, the slow pointer moves one step and the fast pointer moves two steps. This gives us two conclusions:

1. If the LinkedList doesn't have a cycle in it, the fast pointer will reach the end of the LinkedList before the slow pointer to reveal that there is no cycle in the LinkedList.

2. The slow pointer will never be able to catch up to the fast pointer if there is no cycle in the LinkedList.

If the LinkedList has a cycle, the fast pointer enters the cycle first, followed by the slow pointer. After this, both pointers will keep moving in the cycle infinitely. If at any stage both of these pointers meet, we can conclude that the LinkedList has a cycle in it. Let's analyze if it is possible for the two pointers to meet. When the fast pointer is approaching the slow pointer from behind we have two possibilities:

1. The fast pointer is one step behind the slow pointer.
2. The fast pointer is two steps behind the slow pointer.

All other distances between the fast and slow pointers will reduce to one of these two possibilities. Let's analyze these scenarios, considering the fast pointer always moves first:

1. If the fast pointer is one step behind the slow pointer: The fast pointer moves two steps and the slow pointer moves one step, and they both meet.
2. If the fast pointer is two steps behind the slow pointer: The fast pointer moves two steps and the slow pointer moves one step. After the moves, the fast pointer will be one step behind the slow pointer, which reduces this scenario to the first scenario. This means that the two pointers will meet in the next iteration.

This concludes that the two pointers will definitely meet if the LinkedList has a cycle. A similar analysis can be done where the slow pointer moves first. Here is a visual representation of the above discussion:

Code

Here is what our algorithm will look like:

Complexity Analysis

Time Complexity

• The algorithm uses two pointers, slow and fast, to traverse the linked list.
• In the worst case (when there is no cycle), the fast pointer will traverse the entire list at twice the speed of the slow pointer. Therefore, the slow pointer moves through N nodes, where N is the number of nodes in the list.
• The time complexity is O(N), where N is the number of nodes in the linked list.

Space Complexity

• The algorithm uses two pointers, slow and fast, which only take up a constant amount of space.
• There are no additional data structures or memory allocations that depend on the size of the input.

Overall space complexity: O(1) (constant space).

Conclusion:

• Time Complexity: O(N)
• Space Complexity: O(1)

Similar Problems

Problem 1: Given the head of a LinkedList with a cycle, find the length of the cycle.

Solution: We can use the above solution to find the cycle in the LinkedList. Once the fast and slow pointers meet, we can save the slow pointer and iterate the whole cycle with another pointer until we see the slow pointer again to find the length of the cycle.

Here is what our algorithm will look like:

Complexity Analysis

Time Complexity

• Phase 1: Detecting the cycle:
  • The algorithm uses two pointers (slow and fast) to detect a cycle. In the worst case (when there is a cycle), the fast pointer moves twice as fast as the slow pointer. Therefore, the two pointers will meet within a linear traversal of the list.
  • Detecting the cycle requires O(N), where N is the number of nodes in the linked list.
• Phase 2: Calculating the cycle length:
  • Once a cycle is detected, the algorithm calculates the length of the cycle by traversing the cycle with a single pointer. This process also takes O(C) time, where C is the length of the cycle.
  • Since C \leq N, this part is also bounded by O(N) in the worst case.

Overall time complexity: O(N), where N is the total number of nodes in the linked list.

Space Complexity

• The algorithm uses two pointers (slow and fast) to detect the cycle and another pointer (current) to calculate the cycle length. These pointers take constant space.
• No additional data structures are used that scale with the input size.

Overall space complexity: O(1) (constant space).