Solution: Linked List Cycle III

Let’s solve the Linked List Cycle III problem using the Fast and Slow Pointers pattern.

We'll cover the following

Statement

Given the head of a linked list, determine the length of the cycle present in the linked list. If there is no cycle, return 0.

A cycle exists in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

Constraints:

  • The number of nodes in the list is in the range [0,104][0, 10^4].

  • −105≤-10^5 \leq Node.value ≤105\leq 10^5

Solution

The fast and slow pointers technique is an efficient method for detecting cycles in a linked list. In this approach, the fast pointer advances two steps at a time, while the slow pointer moves one step at a time. If the list has no cycle, the fast pointer will eventually reach the end (NULL) without meeting the slow pointer. However, if a cycle exists, the fast pointer will eventually catch up to the slow pointer, confirming the presence of a cycle. Once the two pointers meet inside the cycle, this meeting point can be used to determine the cycle’s length. By keeping one pointer fixed at the meeting point and moving the other through the loop one node at a time, we can count the number of steps until the moving pointer returns to the meeting point. This count represents the length of the cycle in the linked list.

The steps of the algorithm are as follows:

  1. Initialize two pointers, fast and slow, pointing at the linked list’s head.

  2. To detect the cycle in the linked list, perform the below steps:

    1. Move the slow pointer one step forward.

    2. Move the fast pointer two steps forward.

    3. If the fast pointer reaches NULL or fast.next is NULL, no cycle exists in the list.

    4. If the slow and fast pointers meet, a cycle has been detected.

  3. After finding the cycle, determine the length of the cycle by performing the following steps:

    1. When a cycle is detected, we fix one pointer at the meeting point (fast).

    2. The slow pointer moves one step forward, initializing length = 1 to count the first step.

    3. The slow pointer continues, moving within the cycle one step at a time. The loop continues until slow reaches the meeting point (fast) again. Each step increments the length counter.

    4. Once the loop completes, length contains the total number of nodes in the cycle. Returns this value.

  4. If no cycle is found, return 0.

Let’s look at the illustration below to better understand the solution.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.