Vivasoft-logo

Implementation of Floyd’s Cycle-Finding Algorithm in Golang

loop in linked list

What is a loop in a linked list

A very common operation in a linked list is to traverse throughout the LinkedList. But when no null value is reached as traversing throughout the linked list, we call this as loops in a linked list. So to detect whether a LinkedList has a loop or not, we can use Floyd’s Cycle-Finding Algorithm also known as a slow-fast pointer or hear tortoise algorithm.

We are implementing Floyd’s Cycle-Finding Algorithm to find loops in a linked list

Linked List

Node & Linked list struct

type Node struct {
    data interface{}
    next *Node
}

type LinkedList struct {
    head *Node
}

Push to a Linked List

func (ll *LinkedList) Push(data interface{}) {
    list := &Node{
        data: data,
    }
    list.next = ll.head
    if ll.head != nil {
        ll.head = list
    }
    ll.head = list

    l := ll.head
    for l.next != nil {
        l = l.next
    }
}

Display the Linked list

func (ll *LinkedList) Display() {
    list := ll.head
    for list != nil {
        fmt.Printf("%+v -> ", list.data)
        list = list.next
    }
    fmt.Println()
}

Detect loops in LinkedList using Floyd’s Cycle-Finding Algorithm

func (ll *LinkedList) DetectLoop() bool {
    slowPtr := ll.head
    fastPtr := ll.head

    for slowPtr != nil && fastPtr != nil && fastPtr.next != nil {
        slowPtr = slowPtr.next
        fastPtr = fastPtr.next.next
        if slowPtr == fastPtr {
            return true
        }
    }
    return false
}

If you like, you can read the same article on my Personal Blog

Main function

func main() {
    link := LinkedList{}
    link.Push(1)
    link.Push(2)
    link.Push(3)
    link.Push(4)
    link.Push(5)

    // creating a loop in the above linked list
    link.head.next.next.next.next.next = link.head  // comment this then for no loop

    if link.DetectLoop() {
        fmt.Println("found loop")
    } else {
        fmt.Println("no loop")
    }
}

// output
found loop

Yml or Yaml for DevOps

As software engineers, we are always learning new tech stacks as we process our careers. Everyone who works on any short of software farm all came across a term called DevOps. As the name suggests, ...

Working with DocuSign, Authorization and Sending Document for Signature

DocuSign is a well known platform where users can send their document for signing via email or your app. I will try to show you how DocuSign authorize an user and how can we send a document to users ...

Worker Pool in Golang

Tags: #advance #topic #golang #goroutine #channels #workerpool #threadpool Often we end up with some work which is so time-consuming that if we’re able to assign, multiple person/worker, to do ...
java web application

Top 9 Practical Benefits Of Using Java Web Application

Java web application frameworks have one of the greatest and largest communities of software engineers in the world. Companies can build a team with the help of this community at ease. There are different communities to help beginners, intermediate as well as expert developers.

Read More