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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Circular Linked List Traversal

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

DSA Java

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class CircularList {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node second = new Node(20);
        Node third = new Node(30);
        head.next = second;
        second.next = third;
        third.next = head; // circular link

        Node current = head;
        int count = 0;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
            count++;
        } while (current != head && count < 10);
        System.out.print("null");
    }
}

A 10 -> 20 -> 30 -> 10 -> 20 -> 30 -> 10 -> 20 -> 30 -> 10 -> 20 -> 30 -> null

B 10 -> 20 -> 30 -> 10 -> 20 -> 30 -> 10 -> 20 -> 30 -> 10 -> null

C 10 -> 20 -> 30 -> 10 -> 20 -> 30 -> null

D 10 -> 20 -> 30 -> null

💡 Hint

The loop runs while count is less than 10 and stops when current returns to head or count reaches 10.

The do-while loop prints 10 -> 20 -> 30 -> and stops when current returns to head after one full cycle (count=3), even though count <10. Then prints null.

🧠 Conceptual

intermediate

Understanding Circular Linked List Traversal Condition

In a circular linked list traversal, why is it important to check both the current node against the head and a count limit in the loop condition?

A To ensure the list is sorted and to count the number of nodes.

B To avoid infinite loops if the list is circular and to limit traversal length.

C To check if the list is empty and to free memory after traversal.

D To reverse the list during traversal and to count duplicates.

💡 Hint

Think about what happens if you only check for current == head in a circular list.

Checking current against head prevents infinite loops by stopping when traversal completes one full cycle. The count limit is a safety to stop traversal if the list is very large or corrupted.

🔧 Debug

advanced

Identify the Bug in Circular Linked List Traversal

What error will occur when running this Java code snippet that attempts to traverse a circular linked list?

DSA Java

Node current = head;
while (current != head) {
    System.out.print(current.data + " -> ");
    current = current.next;
}
System.out.print("null");

A The loop never executes and prints only 'null'.

B The code throws a NullPointerException.

C The loop runs infinitely causing a program hang.

D The code prints the list nodes exactly once.

💡 Hint

Consider the initial condition when current == head.

Since current starts at head, the condition current != head is false initially, so the loop body never runs and only 'null' is printed.

❓ Predict Output

advanced

Output After Modifying Circular Linked List During Traversal

What is the output of this Java code that modifies the circular linked list during traversal?

DSA Java

class Node {
    int data;
    Node next;
    Node(int d) { data = d; next = null; }
}

public class CircularListMod {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        head.next = second;
        second.next = third;
        third.next = head;

        Node current = head;
        int count = 0;
        do {
            System.out.print(current.data + " -> ");
            if (current.data == 2) {
                current.next = head; // break the circle early
            }
            current = current.next;
            count++;
        } while (current != head && count < 10);
        System.out.print("null");
    }
}

A 1 -> 2 -> 3 -> null

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

C 1 -> 2 -> null

D 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> null

💡 Hint

Notice how the next pointer of node with data 2 is changed during traversal.

Prints 1 -> , moves to 2. Prints 2 -> , sets 2.next = head (1), moves current to 1 (head), count=2. current == head stops the loop. Node 3 is skipped. Prints null.

🧠 Conceptual

expert

Why Use Circular Linked List Traversal Instead of Linear?

Which of the following is the best reason to use a circular linked list traversal approach in certain applications?

A To efficiently cycle through elements repeatedly without resetting pointers.

B To reduce memory usage by avoiding null pointers.

C To simplify sorting algorithms by using circular references.

D To prevent data duplication by linking nodes in a circle.

💡 Hint

Think about applications like round-robin scheduling or buffering.

Circular linked lists allow continuous cycling through elements without needing to reset traversal pointers, useful in applications requiring repeated iteration.

Practice

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

easy

A. In a singly linked list, traversal stops when the starting node is reached again.

B. In a circular linked list, traversal stops when the last node's next is null.

C. Traversal is the same for both lists.

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

Solution

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

   Traversal stops when the next pointer is null, indicating the end of the list.

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

   Traversal stops when the traversal reaches the starting node again, since the list loops back.

3. Final Answer:

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

4. Quick Check:

   Stopping condition differs: null vs start node [OK]

Hint: Remember circular lists loop back to start node [OK]

Common Mistakes:

• Stopping traversal at null in circular list
• Confusing stopping conditions between list types
• Assuming circular list ends with null pointer

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

easy

A. Node current = head; do { System.out.println(current.data); current = current.next; } while(current != head);

B. Node current = head; while(current != null) { System.out.println(current.data); current = current.next; }

C. Node current = head.next; while(current != head) { System.out.println(current.data); current = current.next; }

D. Node current = null; do { System.out.println(current.data); current = current.next; } while(current != head);

Solution

1. Step 1: Check initialization and loop condition

   Node current = head; do { System.out.println(current.data); current = current.next; } while(current != head); initializes current to head and uses a do-while loop to print and move until current equals head again, which is correct for circular lists.

2. Step 2: Analyze other options

   Node current = head; while(current != null) { System.out.println(current.data); current = current.next; } uses while(current != null), which is incorrect for circular lists as next is never null. Node current = head.next; while(current != head) { System.out.println(current.data); current = current.next; } starts from head.next and misses printing head data. Node current = null; do { System.out.println(current.data); current = current.next; } while(current != head); initializes current to null, causing NullPointerException.

3. Final Answer:

   Node current = head; do { System.out.println(current.data); current = current.next; } while(current != head); -> Option A

4. Quick Check:

   Use do-while with current != head [OK]

Hint: Use do-while loop starting at head for circular lists [OK]

Common Mistakes:

• Using while(current != null) for circular lists
• Starting traversal from head.next and missing head node
• Initializing current to null causing errors

3. What will be the output of the following code snippet for a circular linked list with nodes containing data 10 -> 20 -> 30 -> back to 10?

Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = head;

Node current = head;
do {
    System.out.print(current.data + " ");
    current = current.next;
} while(current != head);

medium

A. 10 20 30 10

B. 10 20 30

C. 20 30 10

D. 10 20 30 30

Solution

1. Step 1: Understand the circular linked list structure

   The list nodes are 10 -> 20 -> 30, and 30 points back to 10, making it circular.

2. Step 2: Trace the do-while loop output

   Starting at head (10), print 10, move to 20, print 20, move to 30, print 30, move to 10 again. Loop stops when current == head, so 10 is not printed again.

3. Final Answer:

   10 20 30 -> Option B

4. Quick Check:

   Print nodes once until back to start [OK]

Hint: Do-while prints all nodes once before stopping [OK]

Common Mistakes:

• Printing the start node twice
• Missing the first node in output
• Printing extra nodes beyond the loop

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

Node current = head;
while(current != head) {
    System.out.print(current.data + " ");
    current = current.next;
}

medium

A. The loop never executes because current == head initially.

B. The loop causes infinite printing of nodes.

C. The code throws NullPointerException.

D. The loop skips the last node.

Solution

1. Step 1: Analyze loop condition with initial current value

   current is initialized to head, so current != head is false at start, loop body never runs.

2. Step 2: Understand correct loop for circular list traversal

   Use do-while loop to ensure at least one iteration, since current starts at head.

3. Final Answer:

   The loop never executes because current == head initially. -> Option A

4. Quick Check:

   while(current != head) false at start [OK]

Hint: Use do-while to run loop at least once [OK]

Common Mistakes:

• Using while instead of do-while for circular lists
• Not printing the first node
• Assuming loop runs when condition false initially

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

hard

A. Initialize sum=0; Node current=head.next; while(current != head) { sum += current.data; current = current.next; } return sum;

B. Initialize sum=0; Node current=head; while(current != null) { sum += current.data; current = current.next; } return sum;

C. Initialize sum=0; Node current=head; do { sum += current.data; current = current.next; } while(current != head); return sum;

D. Initialize sum=0; Node current=null; do { sum += current.data; current = current.next; } while(current != head); return sum;

Solution

1. Step 1: Understand traversal stopping condition for circular list

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

2. Step 2: Analyze each option's traversal logic

   Initialize sum=0; Node current=head; do { sum += current.data; current = current.next; } while(current != head); return sum; uses do-while starting at head, summing all nodes once. Initialize sum=0; Node current=head; while(current != null) { sum += current.data; current = current.next; } return sum; uses while(current != null), which never happens in circular list. Initialize sum=0; Node current=head.next; while(current != head) { sum += current.data; current = current.next; } return sum; starts at head.next, missing head's data. Initialize sum=0; Node current=null; do { sum += current.data; current = current.next; } while(current != head); return sum; initializes current to null causing error.

3. Final Answer:

   Initialize sum=0; Node current=head; do { sum += current.data; current = current.next; } while(current != head); return sum; -> Option C

4. Quick Check:

   Use do-while with current != head for full traversal [OK]

Hint: Sum with do-while loop until current equals head [OK]

Common Mistakes:

• Using while(current != null) causing infinite loop
• Skipping head node in sum calculation
• Initializing current to null causing errors