Tag: cycle

Traversing linked list is easy but what would happen if there is a cycle in the linked list?
It will just fall into an infinity loop if traversing is implemented without a cycle prevention code.
Thankfully, there is already a known algorithm for this kind of problem.

How to detect if a cycle exists?

Suppose there is a linked list that has a cycle like below.
Now the question is how to detect the cycle.

Let’s first think about what would happen if there is a cycle.

Iterating linked list typically happens in a while loop like these steps.

1. Check if the node is valid (not null)
2. Process node
3. Move on to next node and do #1,2

Normally iteration will be done once it reaches the end of the list of which next node is null.
However, it will fall into an infinite loop if there is a cycle since there won’t be any null node.

Then, the key is that we shouldn’t visit a node if it was already visited.
How do we detect visited nodes?
The easy answer is to have a cache (map, array or whatever) that keeps track of visited nodes.

So there will be an additional step for cycle detection

1. Check if the node is valid (not null)
2. Process node
3. Move on to next node
4. Check if this node is already visited. If yes then there is a cycle.

What is the time complexity of this problem? O(n). We only need to iterate once.
What is the space complexity of this problem? O(n). Potentially we need to keep track of all visited nodes.

Can we do better?

We cannot do better on time complexity because you need to iterate the list at least once.
However, there is definitely a way to improve space complexity.
In fact, we can solve this problem with O(1) space complexity.

How can we do that?
Think about two people running on a circular track.
And let’s say one person is able to run twice faster than the other.
Then what would happen in that case?
The faster runner will catch the slow runner at the start point after 1 lap of slow person since the faster runner is able to run track twice while the slow runner finishes 1 lap.
We can apply exact same principle to detect a cycle in a linked list.
If we have two pointers that one pointer iterates twice faster than the other faster pointer will catch up slower pointer once it completes 1 lap.

How to find out where the cycle starts?

I think some visualization will do a much better job than a verbal explanation.
So let’s take a look.

The cycle may start after a few nodes.
But as you can see in the picture, the number of nodes before cycle essentially means the number of nodes before cycle start node where two pointers begin iteration.

The above picture shows you that node 15 will be the location where two pointers will meet.
Then, all we need to do is have another pointer at the start of the linked list and iterate both pointer 1 (slow pointer) and 3rd pointer until they meet which is the cycle node!

Code Example

struct Node 
{
    int val;
    Node *next;
    Node(int x) : val(x), next(0) {}
};

Node *detectCycle(Node *head) 
{
    if (!head)
    {
        return 0;
    }

    Node *iter1 = head->next;
    Node *iter2 = head->next ? head->next->next : 0;

    while (iter1 && iter2)
    {
        // cycle found!
        if (iter1 == iter2)
        {
            break;
        }

        iter1 = iter1->next;
        iter2 = iter2->next ? iter2->next->next : 0;
    }

    // no cycle
    if (!iter1 || !iter2)
    {
        return 0;
    }

    Node *cycleNode = head;

    while (iter1 != cycleNode)
    {
        iter1 = iter1->next;
        cycleNode = cycleNode->next;
    }

    return cycleNode;
}