Traversal of Circular Linked List in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a circular linked list?

A circular linked list is a linked list where the last node points back to the first node, forming a circle. There is no null at the end.

beginner

How do you know when to stop traversing a circular linked list?

You stop when you reach the starting node again after moving forward. This prevents infinite loops.

beginner

Show the basic steps to traverse a circular linked list.

1. Start at the head node.
2. Visit the current node.
3. Move to the next node.
4. Repeat until you reach the head node again.

intermediate

Why is traversal of a circular linked list different from a singly linked list?

Because a circular linked list has no end (no null), you must check if you returned to the start node to stop. In singly linked lists, you stop at null.

intermediate

What happens if you forget to check for the start node during traversal?

The traversal will continue forever, causing an infinite loop because the list is circular.

In a circular linked list, what does the last node point to?

A The first node

B Null

C A random node

D Itself

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

When traversing a circular linked list, how do you know when to stop?

A After a fixed number of steps

B When you reach null

C When you reach the start node again

D When the next node is undefined

Traversal stops when you reach the start node again to avoid infinite loops.

What is the risk if you do not check for the start node during traversal?

A You might skip nodes

B You will enter an infinite loop

C You might get an error

D Traversal will stop early

Not checking for the start node causes infinite traversal because the list loops endlessly.

Which of these is NOT true about circular linked lists?

A They form a closed loop

B They can be traversed infinitely without a stop condition

C They have no null at the end

D They always have a tail node pointing to null

Circular linked lists do not have a tail node pointing to null; the last node points to the first node.

What is the first step in traversing a circular linked list?

A Start at the head node

B Check if the list is empty

C Move to the last node

D Set the next pointer to null

Traversal always starts at the head node.

Explain how to traverse a circular linked list safely without causing an infinite loop.

Think about what makes circular linked lists different from normal linked lists.

Describe the difference between traversing a singly linked list and a circular linked list.

Focus on how the end of the list is marked in each type.

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