Traversal of Circular Linked List in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of traversing a circular linked list with 3 nodes

What is the printed output of the following Go code that traverses a circular linked list with 3 nodes?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    next *Node
}
func main() {
    n1 := &Node{data: 1}
    n2 := &Node{data: 2}
    n3 := &Node{data: 3}
    n1.next = n2
    n2.next = n3
    n3.next = n1 // circular link
    current := n1
    count := 0
    for {
        fmt.Print(current.data)
        if count < 2 {
            fmt.Print(" -> ")
        }
        current = current.next
        count++
        if current == n1 {
            break
        }
    }
    fmt.Print(" -> null")
}

A 1 -> 2 -> 3 -> null

B 1 -> 2 -> 3 -> 1 -> null

C 1 -> 2 -> null

D 1 -> 2 -> 3 -> 4 -> null

💡 Hint

Remember that traversal stops when the current node reaches the start node again.

The code prints nodes 1, 2, and 3 once each, then stops because it detects the circular link back to the start node n1. So the output is '1 -> 2 -> 3 -> null'.

🧠 Conceptual

intermediate

Why use a do-while style loop for circular linked list traversal?

In Go, which reason best explains why a do-while style loop (executing at least once before checking condition) is preferred for traversing a circular linked list?

A Because the list has no end, so we must process the first node before checking if we completed a full cycle.

B Because Go does not support for loops with conditions.

C Because circular linked lists always have only one node.

D Because the last node points to nil, so we must check for nil first.

💡 Hint

Think about how to detect when you have visited all nodes exactly once in a circle.

In a circular linked list, there is no nil to mark the end. We must process the first node before checking if we returned to it, so a do-while style loop ensures the first node is processed.

🔧 Debug

advanced

Identify the bug causing infinite loop in circular linked list traversal

What is the bug in this Go code that causes an infinite loop when traversing a circular linked list?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    next *Node
}
func main() {
    n1 := &Node{data: 1}
    n2 := &Node{data: 2}
    n3 := &Node{data: 3}
    n1.next = n2
    n2.next = n3
    n3.next = n1
    current := n1
    for current != nil {
        fmt.Print(current.data, " -> ")
        current = current.next
    }
    fmt.Print("null")
}

A The print statement is missing a newline causing output issues.

B The nodes are not linked correctly; n3.next should be nil.

C The variable 'current' is not initialized before the loop.

D The loop condition 'current != nil' never becomes false because the list is circular.

💡 Hint

Think about what happens when you check for nil in a circular linked list.

Since the list is circular, current never becomes nil, so the loop never ends, causing an infinite loop.

❓ Predict Output

advanced

Output after inserting a node in a circular linked list

What is the printed output after inserting a new node with data 4 after node with data 2 in this circular linked list traversal?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    next *Node
}
func main() {
    n1 := &Node{data: 1}
    n2 := &Node{data: 2}
    n3 := &Node{data: 3}
    n1.next = n2
    n2.next = n3
    n3.next = n1
    // Insert new node with data 4 after n2
    n4 := &Node{data: 4}
    n4.next = n2.next
    n2.next = n4
    current := n1
    for {
        fmt.Print(current.data)
        if current.next != n1 {
            fmt.Print(" -> ")
        }
        current = current.next
        if current == n1 {
            break
        }
    }
    fmt.Print(" -> null")
}

A 1 -> 2 -> 3 -> 4 -> null

B 1 -> 2 -> 3 -> null

C 1 -> 2 -> 4 -> 3 -> null

D 1 -> 4 -> 2 -> 3 -> null

💡 Hint

Check the order of nodes after insertion carefully.

The new node 4 is inserted after node 2, so the order is 1 -> 2 -> 4 -> 3 -> null.

🧠 Conceptual

expert

Detecting loop in a singly linked list using Floyd's cycle-finding algorithm

Which statement best describes how Floyd's cycle-finding algorithm detects a loop in a singly linked list?

A A pointer moves and marks visited nodes; if a node is revisited, a loop exists.

B Two pointers move at different speeds; if they meet, a loop exists.

C The list is reversed and compared to the original; if equal, a loop exists.

D The list length is counted; if it exceeds a threshold, a loop exists.

💡 Hint

Think about how two pointers moving at different speeds can detect cycles.

Floyd's algorithm uses a slow pointer moving one step and a fast pointer moving two steps; if they meet, the list has a cycle.

Practice

1. What is the main difference between a circular linked list and a regular singly linked list?

easy

A. In a circular linked list, the last node points back to the first node.

B. In a circular linked list, nodes have two pointers instead of one.

C. In a circular linked list, nodes are stored in an array.

D. In a circular linked list, the first node points to null.

Solution

1. Step 1: Understand the structure of a circular linked list

   A circular linked list connects the last node back to the first node, forming a circle.

2. Step 2: Compare with a regular singly linked list

   A regular singly linked list ends with a node pointing to null, not back to the first node.

3. Final Answer:

   In a circular linked list, the last node points back to the first node. -> Option A

4. Quick Check:

   Circular list loops back = D [OK]

Hint: Last node points to first node in circular list [OK]

Common Mistakes:

• Thinking circular list nodes have two pointers
• Confusing circular list with doubly linked list
• Assuming last node points to null

2. Which of the following Go code snippets correctly starts traversal of a circular linked list from the head node?

easy

A. current := head
for current != head {
fmt.Println(current.data)
current = current.next
}

B. current := head
for current.next != nil {
fmt.Println(current.data)
current = current.next
}

C. current := head
for current != nil {
fmt.Println(current.data)
current = current.next
if current == head {
break
}
}

D. current := head
for current != nil {
fmt.Println(current.data)
current = current.next
}

Solution

1. Step 1: Identify correct loop condition for circular list

   Traversal must stop when current returns to head to avoid infinite loop.

2. Step 2: Check code options

   current := head for current != nil { fmt.Println(current.data) current = current.next if current == head { break } } uses a break when current equals head, correctly stopping traversal.

3. Final Answer:

   current := head for current != nil { fmt.Println(current.data) current = current.next if current == head { break } } -> Option C

4. Quick Check:

   Stop when current == head = A [OK]

Hint: Stop traversal when current node equals head [OK]

Common Mistakes:

• Using nil as stop condition in circular list
• Not breaking loop causing infinite traversal
• Incorrect loop condition skipping nodes

3. What will be the output of the following Go code snippet that traverses a circular linked list with nodes containing values 10, 20, 30?

type Node struct {
    data int
    next *Node
}

func main() {
    n1 := &Node{data: 10}
    n2 := &Node{data: 20}
    n3 := &Node{data: 30}
    n1.next = n2
    n2.next = n3
    n3.next = n1

    current := n1
    for {
        fmt.Print(current.data, " ")
        current = current.next
        if current == n1 {
            break
        }
    }
}

medium

A. 20 30 10

B. 10 20 30

C. 10 20 30 10

D. Runtime error

Solution

1. Step 1: Understand the circular linked list setup

   Nodes 10 -> 20 -> 30 -> back to 10 form a circle.

2. Step 2: Trace the loop output

   Loop prints current.data then moves to next. Stops when current == n1 again, so prints 10, 20, 30 once.

3. Final Answer:

   10 20 30 -> Option B

4. Quick Check:

   Print nodes once before loop breaks = C [OK]

Hint: Print until current equals start node again [OK]

Common Mistakes:

• Printing extra node after loop break
• Starting traversal from wrong node
• Confusing output order

4. The following Go code attempts to traverse a circular linked list but causes an infinite loop. What is the error?

current := head
for current != nil {
    fmt.Println(current.data)
    current = current.next
}

medium

A. The code should use a for-range loop instead.

B. The code should print after updating current.

C. The list is not circular, so nil check is correct.

D. The loop condition should check if current equals head to stop.

Solution

1. Step 1: Analyze loop condition for circular list

   Checking current != nil never becomes false in circular list, causing infinite loop.

2. Step 2: Correct stopping condition

   Loop should stop when current returns to head node to avoid infinite traversal.

3. Final Answer:

   The loop condition should check if current equals head to stop. -> Option D

4. Quick Check:

   Stop when current == head to avoid infinite loop [OK]

Hint: Use current == head to break loop in circular list [OK]

Common Mistakes:

• Using nil as loop end in circular list
• Not breaking loop causing infinite print
• Misplacing print statement

5. Given a circular linked list where each node contains an integer, write a Go function to find the sum of all node values. Which approach correctly handles traversal without infinite looping?

hard

A. Start from head, add node data, move to next, stop when current equals head again.

B. Start from head, add node data, move to next, stop when current is nil.

C. Use recursion without base case to sum nodes.

D. Traverse nodes twice to ensure all are counted.

Solution

1. Step 1: Understand traversal in circular linked list

   Traversal must stop when current node equals head again to avoid infinite loop.

2. Step 2: Summation logic

   Start at head, add each node's data to sum, move to next node, stop when back at head.

3. Final Answer:

   Start from head, add node data, move to next, stop when current equals head again. -> Option A

4. Quick Check:

   Stop at head to sum all nodes once [OK]

Hint: Stop traversal when current equals head to sum nodes [OK]

Common Mistakes:

• Stopping at nil causing infinite loop
• Using recursion without base case
• Traversing nodes multiple times