15 Jun

Detecting a loop in a linked list

I was recently asked about Floyd’s cycle-finding algorithm, see here for details. In particular the person wanted to know what speeds the two pointers could move at for the algorithm to work. In Floyd’s algorithm the pointers move 1 step and 2 steps at a time respectively.

It’s an interesting question which touches on an element of number theory called modulo arithmetic and the study of congruence relations.

linked list

In Floyd’s algorithm the “hare” and “tortoise” both start at the beginning of the linked list at time, t = 0. At each step the “tortoise” moves 1 place and the hare moves 2 places. Given an arbitrary linked list with a cycle then it is clear the “tortoise” and “hare” won’t meet until they are both in the cycle. For this reason we don’t need to know how many steps it took for both of them to be in the cycle, and we only care from the point that both are in the cycle and we will actually call this t = 0. We will call linked list and linked list the positions that the “tortoise” and “hare” are in on the earliest step that both are in the cycle.

We don’t know how long the cycle is in length, but we will call it, n. We label the first element in the cycle 0, the second 1, the third 2, …., the n-th will be labelled n-1.

If we are at the position labelled n-1 and we move one place then we are at the position labelled 0.

linked list

The above diagram demonstrates what the values of t, n, linked list, linked list will be for the above linked list.

To give a few concrete examples we will pretend to be working with a cycle of length 12 as this gives us the familiar intuition that we have from using our watches.

linked list

however we will relabel the 12 position to be 0.

linked list

Now consider the “tortoise” and “hare” starting at positions 0 and 1 respectively. If the “tortoise” and “hare” move 1 place and 2 places respectively at a time, will they ever meet?

linked list

A quick bit of working with some pen and paper will yield the result that after 11 steps the “tortoise” will be at position 11 and the “hare” would have gone round the watch once and reached position 11 again.

It is true that with the “tortoise” moving 1 place and the “hare” moving 2 places at a time that they will always meet eventually regardless of their start positions (linked list, linked list). The reasons for this will be described later.

What we would like to know is whether other values that the “tortoise” and “hare” can move at each step yields the same result of them meeting eventually.

Consider the start positions as we have above but this time the “tortoise” moves 3 places and the “hare” moves 5 places at a time. Will they meet then?

The positions at each step for the first 15 steps is shown below.

Step Tortoise Hare
0 0 1
1 3 6
2 6 11
3 9 4
4 0 9
5 3 2
6 6 7
7 9 0
8 0 5
9 3 10
10 6 3
11 9 8
12 0 1
13 3 6
14 6 11
15 9 4

You may have noticed that at step 12 we have started to repeat the pattern of step 0. The “tortoise” and “hare” didn’t meet in the first 12 steps and so will never meet. Clearly steps of 3 and 5 don’t work for Floyd’s algorithm and these start positions. However if the “tortoise” started at position 0 and the “hare” at position 2 then it is easy to check that they will meet, so the start positions do matter as well!

Before we write out the problem more formally, let’s first formalise this “clock” arithmetic we have been using implicitly.

We say that linked list if (b – a) is a multiple of n.

The concrete examples we will give will use our familiar clock.

linked list — that is to say that 1pm and 1am look the same on a 12 hour clock. They both use the 1 position.
linked list — that is to say if we start at 1pm and add 24 hours then it is still 1pm but just a day later

In both examples 13 – 1 = 12 and 25 – 1 = 24 are both multiples of 12.

Given the start positions linked list and linked list and the places moved at each step linked list and linked list and a cycle of length n then we are looking for a solution to the following equation:

linked list

This can be rewritten to:

linked list

This is a standard equation in number theory and it has a solution if and only if linked list

The gcd is the greatest common divisor. More information can be found at gcd.

Given that the length of the cycle n and the start positions are arbitrary the only way to guarantee that the above equation has a solution is to ensure that linked list and the only way to guarantee this for all n is to make linked list. In other words the places that the “tortoise” and “hare” move at a time must differ by 1.

This explains why the choice of 1 and 2 work for all linked lists with a cycle, however values such as 4 and 5 will also work. 99 and 100 or even the values 121 and 120!