In a previous post, I wrote about how you can detect a loop in a linked list using Floyd's Hare and Tortoise algorithm. You have two iterators - the hare and the tortoise - one of them runs faster than the other and, if the list has a loop, they will eventually collide. Here is a recap of the algorithm:

public static boolean hasLoop(final Node head) { Node tortoise = head; Node hare = head; while (hare != null && hare.next != null) { tortoise = tortoise.next; hare = hare.next.next; if (hare == tortoise) { // collision return true; } } return false; }

**How do you find the start of the loop?**

Now, let's make this problem more interesting by finding the node at the beginning of the loop.

Consider the following illustration of a linked list with a loop. We need to find the start of the loop, which is 3.

0 - 1 - 2 - 3 / \ 10 4 | | 9 5 | | 8 6 \ / 7

We know that the `hare`

runs twice as fast as the `tortoise`

. Let's say that the `tortoise`

enters the loop after `k`

steps. Then the `hare`

has taken `2k`

steps in total and is, therefore, `k`

steps ahead of the `tortoise`

within the loop. This means that `hare`

and `tortoise`

are `LOOP_SIZE - k`

nodes away from each other. Since `hare`

moves two nodes for each node that `tortoise`

moves, they move one node closer to each on each turn and will meet after `LOOP_SIZE - k`

turns, and both will be `k`

nodes from the start of the loop at that point. The start of the loop is also `k`

nodes from the beginning of the list.

In my example, the `tortoise`

enters the loop (node 3) after 3 steps. At that stage, the `hare`

has taken 6 steps in total and is at node 6. They collide at node 8 after 5 steps (`LOOP_SIZE = 8`

, `k = 3`

, `LOOP_SIZE - k = 5`

). The start of the loop is 3 nodes away from the point of collision and also 3 nodes away from the head of the list.

So, if we keep the `hare`

where it is (at the point of collision) and move the `tortoise`

back to the beginning of the list, and then move each of them one step at a time, they will collide at the start of the loop!

Here is the algorithm:

public static Node findLoopStart(final Node head) { Node tortoise = head; Node hare = head; boolean hasLoop = false; while (hare != null && hare.next != null) { tortoise = tortoise.next; hare = hare.next.next; if (hare == tortoise) { hasLoop = true; break; } } if (hasLoop) { tortoise = head; while (tortoise != hare) { tortoise = tortoise.next; hare = hare.next; } return tortoise; } return null; }