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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Circular Linked List Traversal

What is the printed output of the following C++ code that traverses a circular linked list?

DSA C++

struct Node {
    int data;
    Node* next;
};

#include <iostream>

int main() {
    Node* head = new Node{1, nullptr};
    Node* second = new Node{2, nullptr};
    Node* third = new Node{3, nullptr};

    head->next = second;
    second->next = third;
    third->next = head; // circular link

    Node* temp = head;
    do {
        std::cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    std::cout << "null" << std::endl;

    return 0;
}

A 1 -> 2 -> null

B Runtime error due to infinite loop

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

D 1 -> 2 -> 3 -> null

💡 Hint

The loop stops when the traversal returns to the head node.

The do-while loop prints each node's data once and stops when it reaches the head again, preventing infinite loops in circular lists.

🧠 Conceptual

intermediate

Understanding Circular Linked List Traversal Condition

In a circular linked list traversal, why is the condition usually written as while (temp != head) instead of while (temp != nullptr)?

A Because the last node's next pointer points back to head, not nullptr, so nullptr is never reached.

B Because nullptr is used only in doubly linked lists, not circular linked lists.

C Because head is always nullptr in circular linked lists.

D Because the traversal must stop when temp is nullptr to avoid infinite loops.

💡 Hint

Think about what the last node points to in a circular linked list.

In circular linked lists, the last node points back to the head, so nullptr is never encountered during traversal. The loop stops when temp equals head again.

🔧 Debug

advanced

Identify the Bug in Circular Linked List Traversal

What error will occur when running this traversal code on a circular linked list?

DSA C++

Node* temp = head;
while (temp != nullptr) {
    std::cout << temp->data << " -> ";
    temp = temp->next;
}
std::cout << "null" << std::endl;

A Runtime error due to null pointer dereference

B Compilation error due to missing semicolon

C Infinite loop because temp never becomes nullptr in circular linked list

D Prints all nodes correctly and stops

💡 Hint

Consider what happens to temp in a circular linked list.

Since the last node points back to head, temp never becomes nullptr, causing an infinite loop.

❓ Predict Output

advanced

Output After Inserting Node in Circular Linked List

Given the circular linked list 1 -> 2 -> 3 -> back to 1, what is the output after inserting a new node with value 4 after node with value 2 and traversing?

DSA C++

struct Node {
    int data;
    Node* next;
};

#include <iostream>

int main() {
    Node* head = new Node{1, nullptr};
    Node* second = new Node{2, nullptr};
    Node* third = new Node{3, nullptr};

    head->next = second;
    second->next = third;
    third->next = head;

    // Insert new node with value 4 after second
    Node* newNode = new Node{4, second->next};
    second->next = newNode;

    Node* temp = head;
    do {
        std::cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    std::cout << "null" << std::endl;

    return 0;
}

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

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

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

D 1 -> 2 -> 3 -> null

💡 Hint

The new node is inserted after node 2, so it appears between 2 and 3.

The new node with value 4 is linked after node 2 and before node 3, so traversal prints 1, 2, 4, 3.

🧠 Conceptual

expert

Why Use Circular Linked Lists Over Linear Linked Lists?

Which of the following is the best reason to use a circular linked list instead of a linear linked list?

A To save memory by not storing a nullptr at the end

B To easily loop through the list multiple times without resetting the pointer

C Because circular linked lists are faster for all operations

D Because circular linked lists do not require a head pointer

💡 Hint

Think about continuous traversal without stopping.

Circular linked lists allow continuous traversal from any node without needing to reset to head, useful in applications like round-robin scheduling.

Practice

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

easy

A. In a circular linked list, traversal stops at the last node with NULL pointer.

B. In a circular linked list, traversal requires a double pointer.

C. In a circular linked list, traversal stops when the starting node is reached again.

D. In a circular linked list, traversal is done backwards only.

Solution

1. Step 1: Understand traversal stopping condition for singly linked list

   In a singly linked list, traversal stops when the next pointer is NULL, indicating the end.

2. Step 2: Understand traversal stopping condition for circular linked list

   In a circular linked list, the last node points back to the first node, so traversal stops when we reach the starting node again to avoid infinite loop.

3. Final Answer:

   In a circular linked list, traversal stops when the starting node is reached again. -> Option C

4. Quick Check:

   Traversal stops at start node in circular list = B [OK]

Hint: Stop traversal when you reach the start node again [OK]

Common Mistakes:

• Stopping traversal at NULL pointer in circular list
• Not checking for start node to end traversal
• Assuming circular list traversal is backward

2. Which of the following is the correct syntax to traverse a circular linked list starting from node head in C++?

easy

A. do { /* process node */ head = head->next; } while(head != NULL);

B. do { /* process node */ head = head->next; } while(head != start);

C. while(head != NULL) { /* process node */ head = head->next; }

D. for(Node* temp = head; temp != NULL; temp = temp->next) { /* process node */ }

Solution

1. Step 1: Identify traversal loop type for circular linked list

   Traversal must use a do-while loop to process the start node before checking the condition.

2. Step 2: Check loop condition for circular list traversal

   The loop continues until the pointer returns to the start node, not NULL.

3. Final Answer:

   do { /* process node */ head = head->next; } while(head != start); -> Option B

4. Quick Check:

   Use do-while and check for start node to traverse circular list [OK]

Hint: Use do-while and check for start node, not NULL [OK]

Common Mistakes:

• Using while loop with NULL condition
• Using for loop with NULL condition
• Not processing the start node before condition check

3. What will be the output of the following C++ code that traverses a circular linked list?

#include <iostream>

struct Node {
  int data;
  Node* next;
};

int main() {
  Node n1{1, nullptr}, n2{2, nullptr}, n3{3, nullptr};
  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n1; // circular link

  Node* temp = &n1;
  do {
    std::cout << temp->data << " ";
    temp = temp->next;
  } while(temp != &n1);
  return 0;
}

medium

A. 1 2 3

B. 1 2 3 1

C. 1 2

D. Runtime error

Solution

1. Step 1: Understand the circular linked list structure

   Nodes 1, 2, 3 are linked circularly: 1->2->3->1.

2. Step 2: Trace the do-while traversal

   Traversal starts at node 1, prints 1, moves to 2, prints 2, moves to 3, prints 3, then moves back to 1 and stops.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Print nodes until back to start = 1 2 3 [OK]

Hint: Print nodes until you reach start node again [OK]

Common Mistakes:

• Printing the start node twice
• Stopping traversal early
• Confusing circular with NULL-terminated list

4. Identify the error in the following code snippet for traversing a circular linked list starting at head:

Node* temp = head;
while(temp != head) {
  std::cout << temp->data << " ";
  temp = temp->next;
}

medium

A. The loop misses printing the last node.

B. The loop causes infinite printing of nodes.

C. The code will cause a segmentation fault.

D. The loop never executes because condition is false initially.

Solution

1. Step 1: Analyze the loop condition and initialization

   temp is initialized to head, but the loop condition is while(temp != head), which is false at start.

2. Step 2: Understand loop execution

   Since condition is false initially, the loop body never executes and no nodes are printed.

3. Final Answer:

   The loop never executes because condition is false initially. -> Option D

4. Quick Check:

   temp == head at start, so while(temp != head) is false [OK]

Hint: Use do-while to process start node first in circular list [OK]

Common Mistakes:

• Using while instead of do-while for circular list
• Not processing the start node
• Assuming loop runs at least once

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

hard

A. Use a do-while loop starting at head, add node data, move to next, stop when back at head.

B. Use a while loop with condition temp != nullptr to sum nodes.

C. Use a for loop from 0 to size-1, summing nodes by moving next pointer.

D. Use recursion without base case to sum nodes.

Solution

1. Step 1: Understand circular list traversal for summation

   Traversal must start at head and continue until we return to head to avoid infinite loops.

2. Step 2: Evaluate each option's approach

   Use a do-while loop starting at head, add node data, move to next, stop when back at head. uses do-while loop checking for return to head, correctly summing all nodes once. Use a while loop with condition temp != nullptr to sum nodes. uses nullptr which never occurs in circular list. Use a for loop from 0 to size-1, summing nodes by moving next pointer. assumes size known but size is not given. Use recursion without base case to sum nodes. causes infinite recursion without base case.

3. Final Answer:

   Use a do-while loop starting at head, add node data, move to next, stop when back at head. -> Option A

4. Quick Check:

   Do-while with head check sums circular list correctly [OK]

Hint: Use do-while and stop when pointer returns to head [OK]

Common Mistakes:

• Using nullptr condition in circular list
• Assuming known size without given data
• Using recursion without base case