To check for the existence of a cycle in Linked List, you can use Floyd cycle detection (tortoise and hare algorithm).
I created a mini-game Tile walker 🏃♂️ that shows the use of Floyd cycle detection, you can check it out here.
Linked list is one of the simplest data structures. The idea behind it is to make related objects connect by holding a pointer or a reference to the next object in a collection.
There are three main types of
- Simple Linked List - each member contains information about the next member in the list (if it exists) with a
nextpointer/reference. The last element’s
nextpointer points to
- Doubly Linked List - same as Simple Linked List, with additional
previouspointer/reference that points to a previous member of the list. The first element’s
previouspointer points to
- Circular Linked List - same as Doubly Linked List, but
previouspointer of the first element in the list points to the last element in the list, and the last element’s
nextpointer points to the first element in the list, effectively connecting the list into a loop.
We are going to use a Simple Linked List for the problem we are going to present.
Let’s take an example of a simple Linked List of integers:
Simple Linked List
Traversal is very simple. We start from the first member, take its value and go on to the next member following the pointer, until the pointer of the member points to null.
In this way we are getting the following result:
1 805, 248, 324, 123, 518
Linked List is not always going exclusively forward. Sometimes you need to point to a member in a list that already exists.
Linked List with a cycle
As we can see in this example, this Linked List does not have an end member, as all members of the list point to some other member, and none of them points to
While traversing the list, you will repeatedly walk over the same list members:
1 2 3 4 5 6 7 8 Start process Wait for input Verify input Process input Notify user Wait for input Verify input ...
In this example members from id
1 to id
4 are connected in a loop, or in other words, they are forming a
Here one natural question arises: how can we detect the existence of a
cycle in a Linked List?
The problem is formally known as
The cycle detection problem.
The easiest solution that can be implemented is to save pointers to a list of members as we traverse the Linked List. In every iteration, we are checking if the pointer to that list member is already present in our set of pointers.
Here is the naive approach for the example above:
|iteration||current set state||current id||element was in set|
|4||[0, 1, 2]||3||no|
|5||[0, 1, 2, 3]||4||no|
|6||[0, 1, 2, 3, 4]||1||yes|
As we can see, we are expanding our set of pointers until we come across the pointer that is already present in the set, or we come across a null pointer, which means that list is cycle-free.
Complexity analysis is very simple for this algorithm:
Time complexity is
O(N), because we need to traverse all list members and this is the low as we can get, so this is already the greatest time complexity.
Space complexity is
O(N), because in the worst case we need to store all list elements in the set until we get to the end of the list that does not have
cycle in itself.
As we can see from the analysis, we can affect only space complexity.
The algorithm that was introduced by Robert Floyd is using 2 pointers with which Linked List is traversed in
O(N) time, but since we are using exactly 2 pointers, space complexity is going to be constant, or
Let’s see how it works.
Both pointers start from the beginning of the list. The first pointer advances one step per iteration, whereas the second pointer advances two steps per iteration. If the faster pointer comes across a
null pointer, it means that
Linked List does not have a cycle in it. Otherwise, these two pointers will meet at some moment and they will point to the same list member, hence proving that there is a cycle.
We can show how it works in an example from above:
|iteration||first pointer||second pointer|
Here you can see the demo animation:
Floyd cycle detection iterations
If there is a
cycle in a LinkedList, we can find out the start of the cycle in the following way:
- reset one pointer to the start of the Linked List
- advance both pointers at the same speed (1 list member per iteration) until they meet
- their meeting point is the start of the
That explanation is probably counter-intuitive, so let’s try to explain what exactly happens here:
Cycle start calculation
For simplicity, the formula we are going to derive here works only for cases where
X <= C. Later we’ll cover the general formula, you can check it here
Let’s express the distance traveled by both slow and fast pointers before they meet each other:
slow_pointer_distance = X + Y
fast_pointer_distance = (X + Y + Z) + Y = X + 2Y + Z
We know that the slow pointer is exactly 2 times slower than the fast pointer. So, when they meet, the fast pointer must travel 2 times greater distance:
fast_pointer_distance = 2 X slow_pointer_distance
With the given equations above, we get:
X + 2Y + Z = 2 (X + Y)
X + 2Y + Z = 2X + 2Y
X + Z = 2X
X = Z
If we translate
Z for what they really are, we get:
First node to
Cycle start == distance from
Pointer meeting point to
Now it should be clear that if we move one pointer to the first node and move pointers at the same speed (one step per iteration), they will meet at the Cycle start!
Finding Cycle start
Once we know the starting point of the
cycle, we can calculate its length in a very simple way.
All we need to do is to:
- start with both pointers from the start of the
- traverse with another pointer until we meet the fixed pointer
Simple as that 😃
In the example above we assumed that
X <= C. In case that
X > C, the formula would change a bit, since the
fast pointer can make
N number of cycle traversals until it finally meets the
slow pointer, where
N > 1 (in general case
N cannot be lower than
1 since faster pointer will go with
2X speed the slow pointer, so it will for sure make at least one round trip of the cycle if the cycle exists).
The fast pointer would travel:
X + N * C + Y
And the slow pointer is covering the distance of:
X + Y
Since the fast pointer covers 2 times the distance of the slow pointer, we get the following equation:
2 (X + Y) = X + N*C + Y
2X + 2Y = X + N*C + Y
X + Y = N*C
X = N*C - Y
(N - 1) C + C, and then
(N - 1) C + (Y + Z)
X = (N - 1) C + (Y + Z)- Y
And finally, we get the general formula for all cases:
X = (N - 1) C + Z
We can notice that for
N == 1, we get the same as before:
X = Z
But what this really means is that distance
X is the same as the number of cycles
N-1 that fast pointer travels + distance
Z. So when advancing one pointer from the start of the list, and another from their meeting point, the second one will travel
N-1 cycles and then meet the first pointer at the start of the cycle.
It doesn’t matter if you didn’t quite catch all of this, here is the demo that can help you out 🙂
When X > C
There is a case where the
cycle start node is the same node as the
pointers meeting point node.
In such a case, we have:
slow_pointer_distance = X
fast_pointer_distance = X + N*C
fast pointer is covering
2X distance of
slow pointer, we have:
2*X = X + N*C
X = N*C
This means that distance from the start of the list to the start of the cycle is exactly the distance
fast pointer traveled around the cycle 😃!
In other words, whenever
X is an exact multiple of cycle length
C, we know that the
pointers meeting point and the
cycle start nodes are the same node.
When Meeting point is same as Cycle start
Here is an educative mini-game Tile Walker that is using
Floyd cycle detection to detect cycle in a Linked List in order to conclude that Tile Walker has exhausted all tiles it will walk over in a game.
You can check out the game here.
And code can be found here.
The player is walking in the same direction until he comes across an obstacle. Then it will make a turn of 90 degrees and continue walking in that direction.
The goal is to set up the board, so the Tile Walker can cover as many tiles as possible.
When a player starts the game, it will simulate how Tile Walker is going over the playfield. Once it’s not able to cover more tiles, the game stops. To detect when this happens, we use Floyd cycle detection, but with a twist, since we need to compare not just the location of the player, but its direction as well.
For more info, please check out the repo here.