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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Traversal on Circular Linked List

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

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

// Create circular linked list: 10 -> 20 -> 30 -> back to 10
const head = new Node(10);
const second = new Node(20);
const third = new Node(30);
head.next = second;
second.next = third;
third.next = head;

// Traverse and print values
let current: Node | null = head;
do {
  console.log(current.value);
  current = current.next;
} while (current !== head);

A Runtime error: infinite loop

B 10\n20\n30\n10

C 10\n20\n30

D 10\n20

💡 Hint

Remember that traversal stops when current node comes back to head.

The traversal uses a do-while loop that prints each node's value and moves to the next node. It stops when it reaches the head node again, so it prints 10, 20, and 30 exactly once each.

🧠 Conceptual

intermediate

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

Why is a do-while loop preferred over a while loop when traversing a circular linked list starting from the head node?

A Because <code>while</code> loops cause infinite loops in circular linked lists.

B Because <code>while</code> loops cannot be used with linked lists.

C Because <code>do-while</code> loops are faster in all cases.

D Because the <code>do-while</code> loop ensures the head node is processed before checking the loop condition.

💡 Hint

Think about when the condition is checked in each loop type.

A do-while loop runs the loop body first before checking the condition. This is important for circular linked lists to process the head node before deciding to stop, avoiding missing the first node.

🔧 Debug

advanced

Identify the bug in circular linked list traversal

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

DSA Typescript

let current: Node | null = head;
while (current !== head) {
  console.log(current.value);
  current = current.next;
}

A No output is printed; loop never runs.

B Infinite loop printing all nodes repeatedly.

C Prints only the head node once.

D Runtime error: current is null.

💡 Hint

Consider the initial condition and when the loop body executes.

The loop condition current !== head is false at the start because current is initialized to head. So the loop body never runs and no output is printed.

❓ Predict Output

advanced

Output after inserting a node in circular linked list

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

DSA Typescript

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

const head = new Node(1);
const second = new Node(2);
const third = new Node(3);
head.next = second;
second.next = third;
third.next = head;

// Insert new node with value 4 after node 2
const newNode = new Node(4);
newNode.next = second.next;
second.next = newNode;

// Traverse and print
let current: Node | null = head;
do {
  console.log(current.value);
  current = current.next;
} while (current !== head);

A 1\n2\n4\n3

B 1\n2\n3\n4

C 1\n4\n2\n3

D 1\n2\n3

💡 Hint

Check the insertion point and how next pointers are updated.

The new node with value 4 is inserted after node 2, so the order becomes 1 -> 2 -> 4 -> 3 -> back to 1. Traversal prints nodes in this order.

🧠 Conceptual

expert

Detecting the end of traversal in circular linked list

In a circular linked list, which method reliably detects when a full traversal is complete without using extra memory?

A Stop traversal when the current node's next pointer is null.

B Stop traversal when the current node is the head node again after the first iteration.

C Stop traversal after a fixed number of steps equal to the list length stored separately.

D Stop traversal when a node's value repeats.

💡 Hint

Think about the structure of a circular linked list and what marks the start/end.

Since circular linked lists have no null next pointers, the traversal ends when the current node returns to the head node after visiting all nodes once.

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, nodes cannot be traversed.

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 last node points back to the first node.

Solution

1. Step 1: Understand linked list types

   A regular singly linked list ends with a node pointing to null, while a circular linked list connects the last node back to the first node.

2. Step 2: Identify the key difference

   This connection makes the list circular, allowing traversal to loop indefinitely.

3. Final Answer:

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

4. Quick Check:

   Circular linked list loops back = A [OK]

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

Common Mistakes:

• Thinking circular lists have two pointers per node
• Confusing circular list with doubly linked list
• Assuming nodes are stored in arrays

2. Which of the following is the correct way to start traversing a circular linked list in TypeScript?

easy

A. let current = head; do { /* process current */ current = current.next; } while(current !== head);

B. let current = head; while(current !== null) { /* process current */ current = current.next; }

C. for(let i = 0; i < length; i++) { /* process node */ }

D. let current = head; while(current.next !== null) { /* process current */ current = current.next; }

Solution

1. Step 1: Understand traversal of circular linked list

   Traversal must start at head and continue until we return to head again, using a do-while loop to ensure at least one iteration.

2. Step 2: Check each option

   let current = head; do { /* process current */ current = current.next; } while(current !== head); uses do-while with condition current !== head, which correctly traverses all nodes once. Others either check for null (wrong for circular) or use for loop without node references.

3. Final Answer:

   let current = head; do { /* process current */ current = current.next; } while(current !== head); -> Option A

4. Quick Check:

   Use do-while until back to head [OK]

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

Common Mistakes:

• Using while loop with null condition in circular list
• Using for loop without node references
• Stopping traversal too early

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

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

const n1 = new Node(10);
const n2 = new Node(20);
const n3 = new Node(30);
n1.next = n2;
n2.next = n3;
n3.next = n1; // circular link

let current = n1;
do {
  console.log(current.value);
  current = current.next!;
} while (current !== n1);

medium

A. 20 30 10

B. 10 20 30 10

C. 10 20 30

D. 10 20

Solution

1. Step 1: Understand the circular linked list structure

   Nodes are linked as 10 -> 20 -> 30 -> back to 10, forming a circle.

2. Step 2: Trace the traversal loop

   Starting at n1 (10), the do-while prints 10, moves to 20, prints 20, moves to 30, prints 30, then moves back to 10. Loop stops because current === n1.

3. Final Answer:

   10 20 30 -> Option C

4. Quick Check:

   Print nodes once until back to start [OK]

Hint: Print nodes until current equals head once [OK]

Common Mistakes:

• Printing the first node twice
• Stopping traversal before last node
• Confusing circular with linear traversal

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

let current = head;
while (current !== head) {
  console.log(current.value);
  current = current.next!;
}

medium

A. The code skips the first node during traversal.

B. The loop never runs because current equals head initially.

C. The code throws a null pointer exception.

D. The loop runs infinitely because condition is always true.

Solution

1. Step 1: Analyze the loop condition

   The while loop condition is current !== head, but current starts as head, so condition is false immediately.

2. Step 2: Understand loop execution

   Since condition is false at start, loop body never executes, so no nodes are processed.

3. Final Answer:

   The loop never runs because current equals head initially. -> Option B

4. Quick Check:

   While loop with current !== head fails at start [OK]

Hint: Use do-while to include first node in circular traversal [OK]

Common Mistakes:

• Using while instead of do-while for circular lists
• Assuming loop runs at least once
• Not checking initial condition carefully

5. Given a circular linked list where each node contains a number, write a TypeScript 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 values, stop when current equals head again.

B. Use a while loop checking current !== null, add values until null is reached.

C. Use a for loop with fixed iterations equal to list length, add values each iteration.

D. Use recursion without a base case to sum nodes.

Solution

1. Step 1: Understand circular list traversal for summation

   Since the list is circular, traversal must stop when we return to the starting node to avoid infinite loops.

2. Step 2: Evaluate each approach

   Use a do-while loop starting at head, add values, stop when current equals head again. uses a do-while loop starting at head and stops when current equals head again, correctly summing all nodes once. Use a while loop checking current !== null, add values until null is reached. checks for null which never occurs in circular lists. Use a for loop with fixed iterations equal to list length, add values each iteration. requires knowing length, which may not be available. Use recursion without a base case to sum nodes. causes infinite recursion.

3. Final Answer:

   Use a do-while loop starting at head, add values, stop when current equals head again. -> Option A

4. Quick Check:

   Do-while loop with stop at head = C [OK]

Hint: Stop traversal when current equals head to avoid infinite loop [OK]

Common Mistakes:

• Using null check in circular list traversal
• Recursing without base case causing stack overflow
• Assuming list length is always known