Detect if a Linked List is Circular in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Go code detecting circular linked list?

Consider the following Go code that checks if a linked list is circular. What will it print?

DSA Go

package main
import "fmt"

type Node struct {
    value int
    next  *Node
}

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

func main() {
    n1 := &Node{value: 1}
    n2 := &Node{value: 2}
    n3 := &Node{value: 3}
    n4 := &Node{value: 4}
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n2 // Creates a cycle
    if isCircular(n1) {
        fmt.Println("Circular")
    } else {
        fmt.Println("Not Circular")
    }
}

A Compilation error

B Not Circular

C Circular

D Runtime panic

💡 Hint

Think about how the fast and slow pointers move and meet in a cycle.

The fast pointer moves two steps and the slow pointer moves one step. Because there is a cycle, they will eventually meet, so the function returns true and prints "Circular".

❓ Predict Output

intermediate

What does this Go code print when the linked list has no cycle?

Analyze the following Go code that checks if a linked list is circular. The list has no cycle. What will it print?

DSA Go

package main
import "fmt"

type Node struct {
    value int
    next  *Node
}

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

func main() {
    n1 := &Node{value: 1}
    n2 := &Node{value: 2}
    n3 := &Node{value: 3}
    n4 := &Node{value: 4}
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = nil // No cycle
    if isCircular(n1) {
        fmt.Println("Circular")
    } else {
        fmt.Println("Not Circular")
    }
}

A Not Circular

B Runtime panic

C Compilation error

D Circular

💡 Hint

No node points back to a previous node, so no cycle exists.

Since n4.next is nil, the list ends normally. The fast pointer reaches nil and the function returns false, printing "Not Circular".

🧠 Conceptual

advanced

Why does Floyd's cycle detection algorithm use two pointers moving at different speeds?

In detecting if a linked list is circular, why does Floyd's algorithm use a slow pointer moving one step and a fast pointer moving two steps?

A To ensure the fast pointer eventually catches up to the slow pointer if a cycle exists

B To reduce memory usage by only using two pointers

C To sort the linked list while detecting cycles

D To reverse the linked list during traversal

💡 Hint

Think about how two runners on a track can meet if one runs faster.

The fast pointer moves faster and will lap the slow pointer inside the cycle, guaranteeing detection if a cycle exists.

❓ Predict Output

advanced

What error does this Go code produce when checking a nil linked list?

What happens when the following Go code runs with a nil linked list (head is nil)?

DSA Go

package main
import "fmt"

type Node struct {
    value int
    next  *Node
}

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

func main() {
    var head *Node = nil
    if isCircular(head) {
        fmt.Println("Circular")
    } else {
        fmt.Println("Not Circular")
    }
}

A Prints "Not Circular"

B Prints "Circular"

C Compilation error: head.next undefined

D Runtime panic: invalid memory address or nil pointer dereference

💡 Hint

Check what happens when head is nil and you try to access head.next.

The code tries to access head.next without checking if head is nil, causing a runtime panic due to nil pointer dereference.

🚀 Application

expert

How many nodes are in the linked list after this code runs?

Given the following Go code that creates a linked list with a cycle, how many unique nodes can be traversed starting from head before repeating?

DSA Go

package main
import "fmt"

type Node struct {
    value int
    next  *Node
}

func main() {
    n1 := &Node{value: 1}
    n2 := &Node{value: 2}
    n3 := &Node{value: 3}
    n4 := &Node{value: 4}
    n5 := &Node{value: 5}
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    n5.next = n3 // cycle starts at n3
    count := 0
    current := n1
    visited := make(map[*Node]bool)
    for current != nil {
        if visited[current] {
            break
        }
        visited[current] = true
        count++
        current = current.next
    }
    fmt.Println(count)
}

A 4

B 5

C 3

D Infinite loop

💡 Hint

Count unique nodes before the cycle repeats.

The cycle starts at node with value 3. Nodes 1,2,3,4,5 are unique before revisiting node 3 again. So count is 5.

Practice

1. What does it mean if a linked list is circular?

easy

A. The last node points back to one of the previous nodes, forming a loop

B. The linked list has no nodes

C. The linked list nodes are sorted in ascending order

D. The linked list has only one node

Solution

1. Step 1: Understand linked list structure

   A linked list is a chain of nodes where each node points to the next node.

2. Step 2: Define circular linked list

   If the last node points back to any previous node, it creates a loop, making the list circular.

3. Final Answer:

   The last node points back to one of the previous nodes, forming a loop -> Option A

4. Quick Check:

   Circular linked list means loop in nodes = D [OK]

Hint: Circular means last node links back inside list [OK]

Common Mistakes:

• Thinking circular means sorted list
• Confusing empty list with circular
• Assuming single node list is always circular

2. Which Go code snippet correctly checks if a linked list is circular using two pointers?

easy

A. for slow != nil && fast != nil { slow = slow.Next; fast = fast.Next; if slow == fast { return true } } return false

B. for slow != nil { slow = slow.Next; if slow == fast { return true } } return false

C. for slow != nil && fast != nil && fast.Next != nil { slow = slow.Next; fast = fast.Next.Next; if slow == fast { return true } } return false

D. for fast != nil && fast.Next != nil { fast = fast.Next.Next; if slow == fast { return true } } return false

Solution

1. Step 1: Understand Floyd's cycle detection

   Use two pointers: slow moves one step, fast moves two steps. If they meet, list is circular.

2. Step 2: Check code correctness

   for slow != nil && fast != nil && fast.Next != nil { slow = slow.Next; fast = fast.Next.Next; if slow == fast { return true } } return false correctly moves slow by one and fast by two steps and checks for equality inside the loop.

3. Final Answer:

   for slow != nil && fast != nil && fast.Next != nil { slow = slow.Next; fast = fast.Next.Next; if slow == fast { return true } } return false -> Option C

4. Quick Check:

   Two pointers moving at different speeds detect loop = B [OK]

Hint: Fast pointer moves twice, slow moves once to detect loop [OK]

Common Mistakes:

• Moving fast pointer only one step
• Not checking fast.Next for nil
• Checking slow == fast outside loop

3. What will be the output of this Go code snippet detecting circular linked list?

type Node struct { Val int; Next *Node }

func isCircular(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
}

// List: 1 -> 2 -> 3 -> 4 -> 2 (loop back to node with value 2)
node1 := &Node{1, nil}
node2 := &Node{2, nil}
node3 := &Node{3, nil}
node4 := &Node{4, nil}
node1.Next = node2
node2.Next = node3
node3.Next = node4
node4.Next = node2

fmt.Println(isCircular(node1))

medium

A. true

B. false

C. runtime error

D. infinite loop

Solution

1. Step 1: Analyze linked list structure

   The last node (node4) points back to node2, creating a loop.

2. Step 2: Trace Floyd's cycle detection

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

3. Final Answer:

   true -> Option A

4. Quick Check:

   Loop exists, so output is true [OK]

Hint: Loop in list means function returns true [OK]

Common Mistakes:

• Assuming no loop returns true
• Confusing pointer equality with value equality
• Ignoring fast.Next nil check

4. Find the bug in this Go code that tries to detect if a linked list is circular:

func isCircular(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 function should return false inside the loop when slow != fast

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

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

D. The fast pointer should start at head.Next instead of head

Solution

1. Step 1: Review loop condition

   The loop only checks fast != nil, but fast.Next might be nil causing runtime error on fast.Next.Next.

2. Step 2: Correct loop condition

   Adding fast.Next != nil in the loop condition prevents nil pointer dereference when accessing fast.Next.Next.

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 to avoid errors [OK]

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

Common Mistakes:

• Not checking fast.Next leads to runtime panic
• Moving slow pointer two steps is incorrect
• Returning false inside loop prematurely

5. Given a linked list where the last node points back to the head node, how can you modify the detection function to also return the length of the loop?

hard

A. Return the total number of nodes in the list without checking for loops

B. Count nodes while traversing from head until reaching nil

C. Use a map to store visited nodes and count duplicates

D. After detecting the loop, keep one pointer fixed and move the other until they meet again, counting steps

Solution

1. Step 1: Detect the loop using two pointers

   Use Floyd's cycle detection to find if slow and fast pointers meet inside the loop.

2. Step 2: Count loop length

   Once pointers meet, keep one pointer fixed and move the other pointer forward until it meets the fixed pointer again, counting the steps taken.

3. Final Answer:

   After detecting the loop, keep one pointer fixed and move the other until they meet again, counting steps -> Option D

4. Quick Check:

   Loop length = steps between pointer meetings [OK]

Hint: Count steps between pointer meetings after loop detected [OK]

Common Mistakes:

• Counting nodes until nil in circular list causes infinite loop
• Using map wastes extra memory
• Returning total nodes ignores loop length