How to detect cycle in a Singly linkedlist

Introduction

As we know each element in a linked list is linked to the next element using a pointer called a next pointer. There’s a chance that next pointer of last node(tail) can point to one of the previous node except the head of linkedlist. By principle tail of a Singly linkedlist should point to a null node.

As we can see in the above illustration a cycle is being formed starting from node-3 to node-8.

Why is cycle in a Singly Linkedlist not good?

Let’s revisit the above illustration of cycle in linkedlist again. As we know, a linkedlist is traversed linearly(one after the other). Let’s see what happens when try to traverse this linkedlist:

• We start from node-1 as it is the head of linkedlist.
• Then we go to node-2 then to node-3 then to node-4 then to node-5 then to node-6 then to node-7 then to node-8.
• Everything is pretty normal till we traverse to node-8 when we go to node-8's next we again reach node-3. As node-8’s next is pointing to node-3.
• From node-3 the whole traversal cycle begins again(node-3 to node-4 to node-5 to node-6 to node-7 to node-8). Now we’re pretty much stuck in a infinite loop situation.

So, the problem with having a cycle in linkedlist is iterating over the same nodes again and again infinitely.

How to detect cycle in a linkedlist?

We can detect cycle in a linkedlist by using a method called Hare and Tortoise also called Fast and Slow Pointer technique.

In Hare and Tortoise or Fast and Slow Pointer technique we take two pointers hare or fast and tortoise or slow respectively. We move the hare pointer two nodes ahead and tortoise one node ahead every iteration. If there’s a cycle in linkedlis then there will be a time when hare or fast and tortoise or slow point to the same node. When that happens we know for sure that there’s a cycle in linkedlist. If there’s no cycle in linkedlist then hare or fast and tortoise or slow will always keep moving forward and never converge at a node.

In order to detect a loop we will write a function which takes in head of a linkedlist and returns true if there’s a cycle and false otherwise.

func HasCycle(head *Node) bool {
    // initialize hare and tortoise same as the head node
    hare, tortoise := head
    // iterate over linkedlist till hare reaches the end of linkedlist
    for tortoise != nil && hare != nil && hare.next != nil {
        // make tortoise move one node ahead
        tortoise = tortoise.next
        // make hare move two nodes ahead
        hare = hare.next.next
        // tortoise and hare are at the same node return true
        if tortoise == hare {
            return true
        }
    }
    // if we have traversed till emd of linkedlist then return false
    return false
}

Let’s see the dry run of this function with the illsutration we’re working with:

Key takeaways from above code:

• We take head of linkedlist as input and iterate over linkedlist using the head.
• We initialize hare and tortoise as the head. This means that initially both hare and tortoise are at the same position.
• We iterate till we reach the end of linkedlist.
• We make tortoise move one node ahead.
• We make hare move two nodes ahead.
• If hare and tortoise are at the same node we return true.
• Otherwise if we reach end of linkedlist it means there’s no cycle hence we return false

Closing words

In the next blogs we’ll see how to find starting node of a cycle in linkedlist.

I hope you enjoyed reading this blog and it added some value.