How does finding a cycle start node in a cycle linked list work

Navigating data structures is a cornerstone of effective programming, and among the most intriguing challenges is understanding and manipulating linked lists. While simple linear linked lists are straightforward, the introduction of a “cycle” – where a node points back to an earlier node in the sequence – transforms them into complex puzzles. Such cycles can lead to infinite loops, memory leaks, and unpredictable program behavior if not properly managed. The critical first step in addressing these issues is not just detecting the presence of a cycle, but more importantly, accurately pinpointing the exact location of the cycle start node. This specific node is the gateway to the looped segment, and its identification is essential for breaking the cycle, analyzing its contents, or even reusing the list efficiently. This article delves deep into the mechanisms, particularly the elegant Floyd’s Tortoise and Hare algorithm, that allow us to precisely locate where a linked list decides to take an unexpected turn back on itself.

Understanding Linked List Cycles and Their Implications

A linked list is a fundamental linear data structure where elements, called nodes, are stored at non-contiguous memory locations and are connected through pointers. Each node typically contains data and a reference (or pointer) to the next node in the sequence. In a standard linked list, the last node’s pointer is null, signifying the end of the list. However, a cycle occurs when a node’s pointer, instead of pointing to null or a subsequent new node, points back to a previously visited node within the list, creating an infinite loop.

The presence of a cycle in a linked list can lead to significant problems. Operations like traversing the list, calculating its length, or even freeing memory can get stuck in an endless loop, consuming resources and potentially crashing the program. For instance, if a garbage collector attempts to traverse a cyclic list, it might never finish, leading to memory exhaustion. Therefore, accurately detecting cycles and, crucially, identifying the cycle start node is paramount for maintaining data integrity and program stability. This problem is a common interview question and a practical challenge in system design.

Historically, various methods have been proposed for cycle detection. A naive approach might involve storing all visited nodes in a hash set; if a node is encountered again, a cycle is detected. While effective, this method requires O(N) auxiliary space, where N is the number of nodes. For large lists or memory-constrained environments, a more space-efficient solution is desirable. This is where algorithms like Floyd’s Tortoise and Hare, also known as the “fast and slow pointer” algorithm, shine, offering an elegant O(1) space complexity solution.

The Core Algorithm: Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)

Floyd’s Cycle-Finding Algorithm is an ingenious method for detecting cycles in a linked list using only a constant amount of extra space. The fundamental idea behind this algorithm involves two pointers, often referred to as the “tortoise” (slow pointer) and the “hare” (fast pointer). Both pointers start at the head of the linked list. The tortoise moves one step at a time, while the hare moves two steps at a time.

If there is no cycle in the linked list, the fast pointer will eventually reach the end of the list (i.e., encounter a null pointer). However, if a cycle exists, the fast pointer will inevitably “catch up” to the slow pointer within the loop. This is because every time the slow pointer advances one step, the fast pointer advances two steps, effectively closing the distance between them by one step within the cycle. Eventually, they must meet at some point inside the cycle.

To find the cycle start node in a linked list, Floyd’s Tortoise and Hare algorithm first uses two pointers (slow and fast) to detect if a cycle exists. If the pointers meet, indicating a cycle, one pointer is then reset to the head of the list. Both pointers then advance one step at a time until they meet again; this meeting point is precisely the start of the cycle. This method is highly efficient, operating in O(N) time complexity and O(1) space complexity, making it ideal for large datasets.

The mathematical intuition behind why they meet is straightforward: imagine the slow pointer is at position ‘x’ and the fast pointer is at ‘y’ within a cycle of length ‘L’. Each step, the distance between them decreases by one (relative to the slow pointer’s speed). Since they are both moving within a finite loop, the fast pointer will eventually lap the slow pointer and meet it. Once they meet, the challenge shifts from mere detection to pinpointing the exact entry point of the loop.

Pinpointing the Cycle Start Node

Detecting a cycle is only half the battle; the real goal is to find the cycle start node. This is where the second phase of Floyd’s algorithm comes into play. Once the fast and slow pointers meet, we know for certain that a cycle exists. Let’s call their meeting point ‘P’.

To find the start of the cycle, we introduce a new pointer, let’s call it ‘start_ptr’, and initialize it to the head of the linked list. The slow pointer, which is currently at ‘P’ (the meeting point), remains there. Now, both ‘start_ptr’ and the ‘slow’ pointer (or a new pointer initialized to the meeting point) advance one step at a time. The crucial insight here is that the distance from the head of the list to the start of the cycle is the same as the distance from the meeting point ‘P’ to the start of the cycle, when traversed from ‘P’ using the same step size. Therefore, the point where ‘start_ptr’ and ‘slow’ (or the pointer from ‘P’) meet again will be the very first node of the cycle.

This property holds true because of the relative speeds and distances covered. If ‘F’ is the distance from the head to the cycle start, ‘L’ is the length of the cycle, and ‘K’ is the distance from the cycle start to the meeting point ‘P’, then:

• Slow pointer travels F + K steps.
• Fast pointer travels F + K + nL steps (where n is the number of times fast pointer has lapped slow pointer).
• Since Fast = 2 Slow, we have 2(F + K) = F + K + nL, which simplifies to F + K = nL.
• This means F = nL - K. If we rearrange, F = (n-1)L + (L-K).

This implies that the distance from the head to the cycle start (F) is equivalent to the distance from the meeting point ‘P’ to the cycle start (L-K) plus some multiples of the cycle length. So, if one pointer starts from the head and another from the meeting point, moving one step at a time, they will inevitably converge at the Question & Answer :
I understand that Tortoise and Hare’s meeting concludes the existence of a loop, but how does moving tortoise to the beginning of linked list while keeping the hare at the meeting place, followed by moving both one step at a time make them meet at the starting point of the cycle?

Let me try to clarify the cycle detection algorithm that is provided at Wikipedia - Tortoise_and_hare in my own words.

How it works

Let’s have a tortoise and a hare (name of the pointers) pointing to the beginning of the list with a cycle, as in the diagram above.

Let’s hypothesize that if we move the tortoise 1 step at a time, and the hare 2 steps at a time, they will eventually meet at a point. Let’s show that first of all this hypothesis is true.

The figure illustrates a list with a cycle. The cycle has a length of n and we are initially m steps away from the cycle. Also, let’s say that the meeting point is k steps away from the cycle beginning and tortoise and hare meets when tortoise has taken i total steps. (Hare would have taken 2i total steps by then.).

The following 2 conditions must hold:

1) i = m + p * n + k 2) 2i = m + q * n + k 

The first one says that the tortoise moves i steps and in these i steps, it first gets to the cycle. Then it goes through the cycle p times for some positive number p. Finally, it goes over k more nodes until it meets hare.

A similar thing is true for hare. It moves 2i steps and in these 2i steps it first gets to the cycle. Then it goes through the cycle q times for some positive number q. Finally, it goes over k more nodes until it meets the tortoise.

As the hare travels with double the speed of the tortoise, and time is constant for both when they reach the meeting point.

So by using simple speed, time and distance relation,

2 ( m + p * n + k ) = m + q * n + k => 2m + 2pn + 2k = m + nq + k => m + k = ( q - 2p ) n 

Among m, n, k, p, q, the first two are properties of the given list. If we can show that there is at least one set of values for k, q, p that makes this equation true we show that the hypothesis is correct.

One such solution set is as follows:

p = 0 q = m k = m n - m 

We can verify that these values work as follows:

m + k = ( q - 2p ) n => m + mn - m = ( m - 2*0) n => mn = mn 

For this set, i is

i = m + p n + k => m + 0 * n + mn - m = mn 

Of course, you should see that this is not necessarily the smallest i possible. In other words, tortoise and hare might have already met before many times. However, since we show that they meet at some point at least once we can say that the hypothesis is correct. So they would have to meet if we move one of them by 1 step, and the other one by 2 steps at a time.

Now we can go to the second part of the algorithm which is how to find the beginning of the cycle.

Cycle Beginning

Once tortoise and hare meet, let’s put tortoise back to the beginning of the list and keep hare where they met (which is k steps away from the cycle beginning).

The hypothesis is that if we let them move at the same speed (1 step for both), the first time they ever meet again will be the cycle beginning.

Let’s prove this hypothesis.

Let’s first assume some oracle tells us what m is.

Then, if we let them move m + k steps, the tortoise would have to arrive at the point they met originally (k steps away from the cycle beginning - see in the figure).

Previously we showed that m + k = (q - 2p) n.

Since m + k steps is a multiple of cycle length n, hare, in the meantime, would go through the cycle (q-2p) times and would come back to the same point (k steps away from the cycle beginning).

Now, instead of letting them move m + k steps, if we let them move only m steps, the tortoise would arrive at the cycle beginning. Hare would be k steps short of completing (q-2p) rotations. Since it started k steps in front of the cycle beginning, the hare would have to arrive at the cycle beginning.

As a result, this explains that they would have to meet at the cycle beginning after some number of steps for the very first time (very first time because the tortoise just arrived at the cycle after m steps and it could never see hare which was already in the cycle).

Now we know that the number of steps we need to move them until they meet turns out to be the distance from the beginning of the list to the cycle beginning, m. Of course, the algorithm does not need to know what m is. It will just move both tortoise and hare one step at a time until they meet. The meeting point has to be the cycle start and the number of steps must be the distance (m) to the cycle beginning. Assuming we know the length of the list, we can also, compute the length of the cycle of subtracting m from the list length.