How to find start of cycle in a Singly linkedlist

Introduction

In the previous blog we saw:

• What is a cycle in linkedlist?
• Why is cycle in a Singly Linkedlist not good?
• How to detect cycle in a linkedlist?

Building up on that in this blog lets see how to find starting node of a cycle in linkedlist.

Finding start of cycle in a linkedlist

In order to find the start of a cycle, we first need to know if there’s a cycle in the linkedlist. For detecting cycle in linkedlist we will use the same function we saw in previous blog post.

After finding if there’s a cycle we will take the node at which both hare and tortoise meet. Then we will initialize tortoise as the head of linkedlist and iterate while moving both hare and tortoise ahead by one node. This loop will continue till hare and tortoise meet again. Wherever they meet again will be the start of cycle in linkedlist.

func GetStartOfCycle(head *Node) *Node {
    // check if cycle exist
    if ok, hare := detectCycle(head); ok {
        // if cycle exist we will get the node at which hare and tortoise meet
        // initialize tortoise as head of linkeldist        
        tortoise := head
        // iterate until tortoise and hare meet again
        for tortoise != hare {
            tortoise, hare = tortoise.next, hare.next
        }
        // return tortoise
        return tortoise
    }
    // if there's no cycle return nil
    return nil    
}

func detectCycle(head *Node) (bool,*Node) {
    // initialize both hare and tortoise as the head of linkedlist
    // iterate till end of linkedlist, that is till hare and hare.next is not nil
    for tortoise, hare := head, head; hare != nil && hare.next != nil; {
        // move tortoise ahead by one and hare by two nodes
        tortoise, hare = tortoise.next, hare.next.next
        // if tortoise and hare meet then return true and node at which they meet
        if tortoise == hare {
            return true, hare
        }
    }
    // if hare and tortoise don't meet then return false and nil
    return false,nil
}

Let’s understand the dry run of GetStartOfCycle function:

• First we check if there’s a cycle in linkedlist. If there’s a cycle then the detectCycle function will return true and node where hare and tortoise met. Consider the same example we had in previous blog as below:

  

• As per above illustration detectCycle will return node-7.
• Now in GetStartOfCycle we will keep the hare pointing to node-7(node returned by detectCycle).
• Then we will initialize tortoise as the head of linkedlist.
• At this point tortoise is at head of linkedlist and hare is at node-7.
• Now we start iterating till hare and tortoise meet again by moving both hare and tortoise ahead by one node.
• After first iteration:
  • Tortoise is at node-2.
  • Hare is at node-8.
• After second iteration:
  • Tortoise is at node-3.
  • Hare is also at node-3, as node-8’s next points to node-3. Check out image below for better understanding:

  

• Our loop will exit and we will return node-3 from GetStartOfCycle. As we can see node-3 is the start of cycle in our example.

Closing words

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

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