Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: LinkedList Cycle

Problem Statement

Why this is a Fast and Slow Pointers problem

Solution

Code

Complexity Analysis

Time Complexity

Space Complexity

Conclusion:

Similar Problems

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.

Image

Constraints:

  • The number of the nodes in the list is in the range [0, 10<sup>4</sup>].
  • -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>

About the input. The test harness builds the list from two lines. The first line lists the node values in order. The second line is the zero-based index of the node that the last node points back to. Any value outside 0 .. n-1, such as -1 or n itself, means the last node points to null and the list has no cycle.

So for [1,2,3,4,5,6] the second line 3 links the tail back to the node holding 4, and the second line 6 is out of range for a six node list, which is why that case has no cycle.

Why this is a Fast and Slow Pointers problem

What the question saysThe signal it matches
"Given the head of a Singly LinkedList"the input is a linked list, which you cannot index into
"determine if the LinkedList has a cycle in it or not"the question mentions a cycle
remembering every node you have already seenyour first idea is a hash set of visited nodes

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:

mediaLink

The list is 1 to 6, and the last node points back to the node holding 4, so there is a cycle. Both pointers start at the head. Slow moves one node at a time, fast moves two.

1 of 5

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

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:

Python3
Python3
. . . .

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).

Denys Stopkin

Denys Stopkin

· a year ago

Why doesn't it have a loop? [1,2,3,4,5,6]

6 The last node loops itself as far as I get from the explanation. Only this->next == nullptr in the last node means there's no loop in the list

Show 1 reply
Faraz Ahmed

Faraz Ahmed

· 3 years ago

iam confused how the fast (object) will be equal to slow(object), coz in javascript two object are never same they have different memory addressess!

1,2,3,4,5,6

in this list, the fast pointer reaches the end, and the fast===slow is not being satisfied,i get it but will fast === slow will be evaluated to true ? if we are comparing two objects?

Show 1 reply
H

hj3yoo

· 5 years ago

For the similar question, I don't think we need to iterate through the cycle again.

The fast pointer travels twice as fast as the slow pointer, and it has covered the same distance that the slow pointer has covered plus an entire cycle. Mathematically, this means that: 2 * d_slow = d_slow + d_cycle, which simplifies to d_cycle = d_slow.

Therefore, we can keep track of how many nodes the slow pointers travelled until the fast pointer meets it and return that value.

Haven't tested in code, but please correct me if I'm wrong.

Show 5 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Why this is a Fast and Slow Pointers problem

Solution

Code

Complexity Analysis

Time Complexity

Space Complexity

Conclusion:

Similar Problems

Complexity Analysis

Time Complexity

Space Complexity