Traversal of Circular Linked List in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start traversal from the head node.

DSA C++

Node* current = [1];

Drag options to blanks, or click blank then click option'

Ahead

Bnullptr

Ctail

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Starting traversal from tail instead of head.

Using nullptr which means no node.

The traversal of a circular linked list starts from the head node.

2fill in blank

medium

Complete the code to print the data of the current node during traversal.

DSA C++

std::cout << current->[1] << " -> ";

Drag options to blanks, or click blank then click option'

Avalue

Bnext

Cprev

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Trying to print 'next' which is a pointer, not data.

Using 'value' which is not defined in the node.

Each node stores data in the 'data' member, which we print.

3fill in blank

hard

Fix the error in the loop condition to stop traversal after one full cycle.

DSA C++

do {
    // process current node
    current = current->next;
} while (current != [1]);

Drag options to blanks, or click blank then click option'

Ahead

Btail

Ccurrent

Dnullptr

Attempts:

3 left

💡 Hint

Common Mistakes

Using nullptr which never matches in circular list.

Comparing with tail which is not the start node.

The loop should continue until we reach the head node again, completing one full circle.

4fill in blank

hard

Fill both blanks to correctly initialize and traverse the circular linked list.

DSA C++

Node* current = [1];
do {
    std::cout << current->data << " -> ";
    current = current->[2];
} while (current != head);

Drag options to blanks, or click blank then click option'

Ahead

Btail

Cnext

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from tail instead of head.

Using 'prev' which moves backward.

Start from head and move to next node each time until back to head.

5fill in blank

hard

Fill all three blanks to create a map of node data to their next node's data for the circular linked list.

DSA C++

std::map<int, int> next_map = {
    {current->[1], current->[2]->[3]
};

Drag options to blanks, or click blank then click option'

Adata

Bnext

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' to get next node.

Mixing up data and next pointers.

Map key is current node's data, value is next node's data.

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