Detect cycle start node in a linked list in Go (Golang)

Table of Contents

Overview

The objective is to find out the cycle start node in a given linked list. A cycle exists in a linked list if the last node in the linked list points to another node in the front

Example

The linked list above has a cycle. The cycle start node is node 2. Below is the approach we can follow

First, detect whether the given linked list has a cycle or not. Have two pointers. One is the slow pointer and the other is a fast pointer. Both point to the head node initially

Now move the slow pointer by 1 node and move the fast pointer by 2 nodes.

slow := slow.Next
fast := fast.Next.Next

If slow and fast pointers are the same at any point in time then the linked list has cyle.

The fast pointer and a slow pointer can only meet at a node that is in the cycle. Let’s assume they meet at node 3. Now get the length of the cycle. The length is 3

Then keep one pointer at the head of the node and the other pointer at a distance of cycle length from it. So one pointer will be added at node 1 and another pointer will be at node 4.

Move both the pointers until they are the same. They will meet at the cycle start node which is Node 2

Program

Here is the program for the same.

package main

import "fmt"

func main() {
	first := initList()
	ele4 := first.AddFront(4)
	first.AddFront(3)
	ele2 := first.AddFront(2)
	first.AddFront(1)

	//Create cycle
	ele4.Next = ele2

	output := cycleStartNode(first.Head)
	fmt.Println(output.Val)

}

type ListNode struct {
	Val  int
	Next *ListNode
}

type SingleList struct {
	Len  int
	Head *ListNode
}

func (s *SingleList) AddFront(num int) *ListNode {
	ele := &ListNode{
		Val: num,
	}
	if s.Head == nil {
		s.Head = ele
	} else {
		ele.Next = s.Head
		s.Head = ele
	}
	s.Len++
	return ele
}

func initList() *SingleList {
	return &SingleList{}
}
func cycleStartNode(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	slow := head
	fast := head

	cycleExists := false

	for slow != nil && fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next

		if slow == fast {
			cycleExists = true
			break
		}
	}

	if !cycleExists {
		return nil
	}

	cycleNode := slow

	curr := cycleNode

	lengthCycle := 1

	for curr.Next != cycleNode {
		lengthCycle++
		curr = curr.Next
	}

	curr = head

	for i := 0; i < lengthCycle; i++ {
		curr = curr.Next
	}

	for head != curr {
		head = head.Next
		curr = curr.Next
	}

	return head
}

Output

Note: Check out our Golang Advanced Tutorial. The tutorials in this series are elaborative and we have tried to cover all concepts with examples. This tutorial is for those who are looking to gain expertise and a solid understanding of golang - Golang Advance Tutorial

Also if you are interested in understanding how all design patterns can be implemented in Golang. If yes, then this post is for you -All Design Patterns Golang

golang