Solution: Start of LinkedList Cycle

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Start of LinkedList Cycle

Table of Contents

Contents are not accessible

Problem Statement

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

Solution

If we know the length of the LinkedList cycle, we can find the start of the cycle through the following steps:

Take two pointers. Let’s call them pointer1 and pointer2.
Initialize both pointers to point to the start of the LinkedList.
We can find the length of the LinkedList cycle using the approach discussed in LinkedList Cycle. Let’s assume that the length of the cycle is ‘K’ nodes.
Move pointer2 ahead by ‘K’ nodes.
Now, keep incrementing pointer1 and pointer2 until they both meet.
As pointer2 is ‘K’ nodes ahead of pointer1, which means, pointer2 must have completed one loop in the cycle when both pointers meet. Their meeting point will be the start of the cycle.

Let’s visually see this with the above-mentioned Example-1:

We can use the algorithm discussed in LinkedList Cycle to find the length of the cycle and then follow the above-mentioned steps to find the start of the cycle.

Code

Here is what our algorithm will look like:

Python3

. . . .

Complexity Analysis

Time Complexity

Phase 1: Cycle detection:
- The algorithm uses Floyd's Tortoise and Hare (fast and slow pointer) approach to detect a cycle in the linked list. Both pointers traverse the list at different speeds, with the fast pointer moving twice as fast as the slow pointer. In the worst case, they traverse the entire list once until they meet inside the cycle or confirm there is no cycle.
- This phase takes $O(N)$ time, where N is the number of nodes in the linked list.
Phase 2: Cycle length calculation:
- After detecting the cycle, the algorithm calculates the cycle's length by traversing the cycle with the slow pointer. The maximum number of steps taken is equal to the length of the cycle, denoted as $C$ . Since $C \leq N$ , this phase is bounded by $O(N)$ time.
Phase 3: Finding the start of the cycle:
- Once the cycle length is known, the algorithm uses two pointers to find the start of the cycle. The first pointer starts from the head, while the second pointer is moved ahead by C nodes. Both pointers then traverse the list one step at a time until they meet at the cycle's start. Since each pointer traverses part of the list, this phase also takes $O(N)$ time.

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

Space Complexity

The algorithm uses a few extra variables, including two pointers (slow and fast) and some helper variables for calculating the cycle length and finding the start of the cycle. These variables require constant space.
No additional data structures that depend on the input size are used.

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

An Alternate Approach

Here is the second approach to solve the "Start of LinkedList Cycle" problem using Floyd’s Tortoise and Hare algorithm. This method employs two pointers moving at different speeds to detect the cycle and identify its starting node.

The algorithm begins by initializing two pointers, slow and fast, both starting at the head of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps. If there is a cycle, these pointers will eventually meet inside the cycle. Once a meeting point is found, the slow pointer is reset to the head, and both pointers move one step at a time. The point where they meet again is the start of the cycle.

Step-by-Step Algorithm

Phase 1: Detecting the Cycle Using Two Pointers

Initialize Pointers:
- Set both slow and fast pointers to the head of the linked list to start traversing from the beginning.
Traverse to Detect Cycle:
- Loop while fast and fast.next are not null:
  - Move slow one step forward.
  - Move fast two steps forward.
  - If slow and fast meet, a cycle is detected and exit the loop.
Check for No Cycle:
- After the loop, if fast is null or fast.next is null, return null as there is no cycle in the list.

Phase 2: Finding the Start of the Cycle

Reset slow Pointer:
- Move slow back to the head of the linked list to begin locating the cycle's start.
Move Both Pointers to Find Cycle Start:
- Loop until slow equals fast:
  - Move slow one step forward.
  - Move fast one step forward.
- When they meet, slow (or fast) points to the cycle's starting node.
Return the Starting Node:
- Return the node where slow and fast meet as the start of the cycle.

Algorithm Walkthrough

Input: List = [1, 2, 3, 4, 5, 6], Cycle Start at Node 3

Linked List Structure:

1 -> 2 -> 3 -> 4 -> 5 -> 6
          ^              |
          |--------------|

Steps:

Initialize Pointers:
- slow = 1, fast = 1
First Iteration:
- Move slow to 2.
- Move fast to 3.
- slow != fast
Second Iteration:
- Move slow to 3.
- Move fast to 5.
- slow != fast
Third Iteration:
- Move slow to 4.
- Move fast to 3 (since fast was at 5, fast.next is 6, and fast.next.next is 3).
- slow != fast
Fourth Iteration:
- Move slow to 5.
- Move fast to 5.
- slow == fast (Cycle detected)
Find Cycle Start:
- Reset slow to 1.
- Move both slow and fast one step at a time:
  - Move slow to 2, fast to 6.
  - Move slow to 3, fast to 3.
- slow == fast at node 3 (Cycle starts here)
Return Cycle Start:
- The start of the cycle is node 3.