Detect Cycle in Linked List Floyd's Algorithm in DSA Go

Mental Model

Use two pointers moving at different speeds to find if a loop exists in a linked list.

Analogy: Imagine two runners on a circular track: one runs slowly, the other runs fast. If the track loops, the fast runner will eventually catch the slow runner.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> back to 3 (cycle starts at node with value 3)

Goal: Detect if the linked list has a cycle using Floyd's algorithm

Step 1: Initialize slow and fast pointers at head (node 1)

1 -> 2 -> 3 -> 4 -> 5 -> back to 3
slow ↑ at 1
fast ↑ at 1

Why: Start both pointers at the beginning to begin traversal

Step 2: Move slow by 1 step to node 2, fast by 2 steps to node 3

1 -> 2 -> 3 -> 4 -> 5 -> back to 3
slow ↑ at 2
fast ↑ at 3

Why: Advance pointers at different speeds to detect cycle

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 5

1 -> 2 -> 3 -> 4 -> 5 -> back to 3
slow ↑ at 3
fast ↑ at 5

Why: Continue advancing pointers; fast moves twice as fast

Step 4: Move slow by 1 step to node 4, fast by 2 steps to node 4 (cycle causes fast to loop back)

1 -> 2 -> 3 -> 4 -> 5 -> back to 3
slow ↑ at 4
fast ↑ at 4

Why: Pointers meet inside the cycle, confirming a loop

Result:

1 -> 2 -> 3 -> 4 -> 5 -> back to 3
slow and fast meet at node 4 -> cycle detected

Annotated Code

DSA Go

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false // empty or single node can't have cycle
	}
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next // move slow by 1
		fast = fast.Next.Next // move fast by 2
		if slow == fast {
			return true // pointers meet, cycle detected
		}
	}
	return false // fast reached end, no cycle
}

func main() {
	// Create nodes
	n1 := &ListNode{Val: 1}
	n2 := &ListNode{Val: 2}
	n3 := &ListNode{Val: 3}
	n4 := &ListNode{Val: 4}
	n5 := &ListNode{Val: 5}

	// Link nodes
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	n4.Next = n5
	n5.Next = n3 // cycle here

	// Check cycle
	fmt.Println(hasCycle(n1))
}

if head == nil || head.Next == nil {

handle empty or single node list - no cycle possible

slow, fast := head, head

initialize two pointers at head

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

loop while fast pointer and its next exist to avoid nil errors

slow = slow.Next // move slow by 1

advance slow pointer by one node

fast = fast.Next.Next // move fast by 2

advance fast pointer by two nodes

if slow == fast {

check if pointers meet indicating a cycle

return true // pointers meet, cycle detected

cycle found, return true

return false // fast reached end, no cycle

no cycle found after traversal

Output

true

Complexity Analysis

Time: O(n) because each node is visited at most twice by slow and fast pointers

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to using a hash set to track visited nodes (O(n) space), Floyd's algorithm uses constant space making it more efficient in memory

Edge Cases

empty list

returns false immediately since no nodes exist

DSA Go

if head == nil || head.Next == nil {

single node without cycle

returns false because a single node cannot form a cycle

DSA Go

if head == nil || head.Next == nil {

two nodes with cycle (second node points back to first)

detects cycle when slow and fast pointers meet

DSA Go

if slow == fast {

When to Use This Pattern

When you need to detect a cycle in a linked list efficiently, Floyd's algorithm is the go-to pattern because it uses two pointers moving at different speeds to find loops without extra memory.

Common Mistakes

Mistake: Not checking if fast or fast.Next is nil before advancing fast pointer
Fix: Add condition 'fast != nil && fast.Next != nil' in the loop to avoid nil pointer errors

Mistake: Moving slow and fast pointers by the same amount
Fix: Move slow by one step and fast by two steps to ensure they meet if a cycle exists

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you want to find loops in linked lists without extra memory.

The fast pointer will catch the slow pointer inside the cycle if one exists.

Practice

1. What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

easy

A. Reverse the linked list and check if it matches the original

B. Count the number of nodes and check if it exceeds a limit

C. Use two pointers moving at different speeds to detect a cycle

D. Use a hash map to store visited nodes

Solution

1. Step 1: Understand Floyd's Algorithm concept

   It uses two pointers, one moving one step at a time (slow), and another moving two steps at a time (fast).

2. Step 2: Detect cycle by pointer meeting

   If the fast pointer meets the slow pointer, it means there is a cycle in the linked list.

3. Final Answer:

   Use two pointers moving at different speeds to detect a cycle -> Option C

4. Quick Check:

   Two pointers at different speeds = cycle detection [OK]

Hint: Two pointers at different speeds detect cycle fast [OK]

Common Mistakes:

• Thinking counting nodes detects cycle
• Assuming reversing list helps detect cycle
• Using extra memory like hash map is not Floyd's method

2. Which of the following Go code snippets correctly initializes the two pointers for Floyd's cycle detection in a linked list named head?

easy

A. slow, fast := head, head

B. slow, fast := head.next, head.next.next

C. slow, fast := head, head.next

D. slow, fast := nil, head

Solution

1. Step 1: Initialize both pointers at head

   Floyd's algorithm starts both slow and fast pointers at the head node.

2. Step 2: Move pointers inside loop, not at initialization

   Moving fast or slow pointer ahead at initialization can skip nodes or cause errors.

3. Final Answer:

   slow, fast := head, head -> Option A

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head before loop [OK]

Common Mistakes:

• Starting fast pointer ahead causing nil pointer errors
• Initializing slow pointer ahead skipping first node
• Setting slow pointer to nil initially

3. What will be the output of the following Go code snippet detecting a cycle in a linked list?

type Node struct {
  val  int
  next *Node
}

func hasCycle(head *Node) bool {
  slow, fast := head, head
  for fast != nil && fast.next != nil {
    slow = slow.next
    fast = fast.next.next
    if slow == fast {
      return true
    }
  }
  return false
}

// Linked list setup
n1 := &Node{val: 1}
n2 := &Node{val: 2}
n3 := &Node{val: 3}
n4 := &Node{val: 4}
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n2 // cycle here

fmt.Println(hasCycle(n1))

medium

A. true

B. false

C. runtime error

D. infinite loop

Solution

1. Step 1: Analyze linked list structure

   The list nodes are connected 1->2->3->4, and 4 points back to 2, creating a cycle.

2. Step 2: Trace Floyd's algorithm behavior

   Slow and fast pointers will eventually meet inside the cycle, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle exists, so output is true [OK]

Hint: Cycle means pointers meet, so return true [OK]

Common Mistakes:

• Assuming no cycle because list looks linear
• Expecting false without tracing pointers
• Confusing cycle detection with list length

4. Identify the bug in this Go code snippet for detecting a cycle in a linked list:

func hasCycle(head *Node) bool {
  slow, fast := head, head
  for fast != nil {
    slow = slow.next
    fast = fast.next.next
    if slow == fast {
      return true
    }
  }
  return false
}

medium

A. The slow pointer should move two steps instead of one

B. The loop condition should check fast.next != nil to avoid nil pointer dereference

C. The fast pointer should move one step instead of two

D. The function should return false inside the loop when pointers don't meet

Solution

1. Step 1: Check loop condition safety

   The loop only checks fast != nil, but fast.next could be nil causing fast.next.next to panic.

2. Step 2: Correct loop condition

   Loop should check both fast != nil and fast.next != nil to safely move fast pointer two steps.

3. Final Answer:

   The loop condition should check fast.next != nil to avoid nil pointer dereference -> Option B

4. Quick Check:

   Check fast and fast.next != nil before moving fast [OK]

Hint: Always check fast.next != nil before fast.next.next [OK]

Common Mistakes:

• Ignoring fast.next nil check causing runtime panic
• Moving slow pointer two steps incorrectly
• Returning false too early inside loop

5. Given a linked list where the cycle starts at node with value 3, how can Floyd's algorithm be extended to find the exact node where the cycle begins?

hard

A. Count nodes until pointers meet and return the count as cycle start position

B. Reverse the linked list and check where reversal breaks to find cycle start

C. Use a hash map to store nodes and find the first repeated node

D. After detecting the cycle, reset one pointer to head and move both one step until they meet at cycle start

Solution

1. Step 1: Detect cycle using Floyd's algorithm

   First, detect if a cycle exists by moving slow and fast pointers until they meet.

2. Step 2: Find cycle start node

   Reset one pointer to head, then move both pointers one step at a time; the node where they meet is the cycle start.

3. Final Answer:

   After detecting the cycle, reset one pointer to head and move both one step until they meet at cycle start -> Option D

4. Quick Check:

   Reset pointer + move one step = cycle start [OK]

Hint: Reset pointer to head after cycle detection to find start [OK]

Common Mistakes:

• Trying to count nodes instead of resetting pointer
• Using extra memory instead of pointer method
• Reversing list which breaks structure