## Sunday, November 06, 2016

### Detecting a Loop in a Linked List

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

boolean hasLoop = false;
while (hare != null && hare.next != null) {
tortoise = tortoise.next;
hare = hare.next.next;
if (hare == tortoise) {
hasLoop = true;
break;
}
}

if (hasLoop) {