Delete a Node from 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.

intermediate

Why is deleting a node from a circular linked list different from a singly linked list?

Because the last node points back to the head, you must update the last node's next pointer if you delete the head. Also, you must handle the circular link carefully to avoid breaking the circle.

beginner

What happens if you delete the only node in a circular linked list?

The list becomes empty, so the head pointer should be set to null or undefined to indicate the list is empty.

beginner

In TypeScript, how do you represent a node in a circular linked list?

You can create a class with a value and a next pointer. For example:<br><code>class Node {<br>  value: number;<br>  next: Node | null;<br>  constructor(value: number) {<br>    this.value = value;<br>    this.next = null;<br>  }<br>}</code>

intermediate

What is the general approach to delete a node with a given value from a circular linked list?

1. If the list is empty, do nothing.
2. If the node to delete is the head, find the last node and update its next pointer.
3. Traverse the list to find the node before the node to delete.
4. Update the previous node's next pointer to skip the deleted node.
5. Handle the case when the node is not found.

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

A The first node

B Null

C Itself

D The second node

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

What should you do if you delete the head node in a circular linked list?

A Set head to null without changing anything else

B Delete the entire list

C Update the last node's next pointer to the new head

D Nothing special is needed

You must update the last node's next pointer to point to the new head to maintain the circular link.

If a circular linked list has only one node and you delete it, what is the new state of the list?

A The list becomes a doubly linked list

B The node points to itself

C The list still has one node

D The list becomes empty

Deleting the only node makes the list empty, so head should be set to null.

Which of these is NOT a step when deleting a node from a circular linked list?

A Break the circular link permanently

B Update the previous node's next pointer

C Traverse to find the node before the node to delete

D Handle the case when the node is not found

You should maintain the circular link; breaking it permanently is incorrect.

In TypeScript, what type should the 'next' pointer have in a circular linked list node?

A boolean

B Node | null

C string

D number

The 'next' pointer should be either another Node or null if the list is empty.

Explain step-by-step how to delete a node with a specific value from a circular linked list.

Think about how the circular link affects pointer updates.

Describe how the circular linked list structure changes when deleting the only node in the list.

Consider what happens to the head and next pointers.

Practice

1. What happens when you delete the only node in a circular linked list?

easy

A. The list becomes empty (null).

B. The list still contains the deleted node.

C. The list points to itself indefinitely.

D. The list throws an error.

Solution

1. Step 1: Understand the single node case

   When there is only one node, it points to itself forming a circle.

2. Step 2: Delete the only node

   Removing this node leaves no nodes, so the list becomes empty (null).

3. Final Answer:

   The list becomes empty (null). -> Option A

4. Quick Check:

   Single node deleted = empty list [OK]

Hint: Deleting last node empties the list [OK]

Common Mistakes:

• Assuming list still has nodes after deleting the only node
• Not setting head to null after deletion

2. Which of the following is the correct way to update the previous node's next pointer when deleting a node in a circular linked list?

easy

A. prev.next = node.next;

B. node.next = prev.next;

C. prev = node.next;

D. node = prev.next;

Solution

1. Step 1: Identify the pointer to update

   To remove a node, the previous node's next pointer must skip the node to delete.

2. Step 2: Update the previous node's next pointer

   Set prev.next to node.next to bypass the node being deleted.

3. Final Answer:

   prev.next = node.next; -> Option A

4. Quick Check:

   prev.next points to node.next [OK]

Hint: Prev node's next skips deleted node [OK]

Common Mistakes:

• Assigning node.next to prev.next instead of the other way
• Changing the node variable instead of prev.next

3. Consider the circular linked list: 10 -> 20 -> 30 -> (back to 10). If we delete the node with value 20, what will be the new list?

medium

A. 10 -> 20 -> 30 -> (back to 10)

B. 10 -> 30 -> (back to 10)

C. 20 -> 30 -> (back to 20)

D. 30 -> 10 -> (back to 30)

Solution

1. Step 1: Identify node to delete and its previous node

   Node with value 20 is between 10 and 30. Previous node is 10.

2. Step 2: Update previous node's next pointer

   Set 10's next pointer to 30, skipping 20.

3. Final Answer:

   10 -> 30 -> (back to 10) -> Option B

4. Quick Check:

   Deleted 20, list links 10 to 30 [OK]

Hint: Link previous node to next of deleted node [OK]

Common Mistakes:

• Not updating the previous node's next pointer
• Deleting wrong node or not updating links

4. Given this TypeScript code snippet to delete a node from a circular linked list, what is the error?

function deleteNode(head: Node | null, key: number): Node | null {
  if (!head) return null;
  let curr = head, prev = null;
  do {
    if (curr.data === key) {
      if (prev) prev.next = curr.next;
      else head = curr.next;
      return head;
    }
    prev = curr;
    curr = curr.next;
  } while (curr !== head);
  return head;
}

medium

A. Does not handle the empty list case.

B. Uses 'do-while' incorrectly causing infinite loop.

C. Returns null even if node is not found.

D. Does not update the tail node's next pointer when deleting head.

Solution

1. Step 1: Analyze deletion of head node

   If deleting head, code sets head to curr.next but does not update tail's next pointer.

2. Step 2: Identify missing tail update

   In circular list, tail's next must point to new head to maintain circularity.

3. Final Answer:

   Does not update the tail node's next pointer when deleting head. -> Option D

4. Quick Check:

   Tail.next must update on head deletion [OK]

Hint: Update tail's next when head is deleted [OK]

Common Mistakes:

• Ignoring tail pointer update after head deletion
• Assuming head change auto-updates tail's next

5. You have a circular linked list with nodes: 5 -> 10 -> 15 -> 20 -> (back to 5). You want to delete the node with value 5 (head node). Which steps correctly delete the head and maintain the circular list?

hard

A. Delete head node and set head to null.

B. Set head to head.next only, no other changes.

C. Find tail node, set tail.next to head.next, update head to head.next.

D. Find tail node, set tail.next to null, update head to head.next.

Solution

1. Step 1: Find the tail node

   Traverse list to find node whose next points to head (value 20).

2. Step 2: Update tail's next pointer and head

   Set tail.next to head.next (node with value 10), then update head to head.next.

3. Final Answer:

   Find tail node, set tail.next to head.next, update head to head.next. -> Option C

4. Quick Check:

   Tail.next points to new head after deletion [OK]

Hint: Update tail.next before changing head [OK]

Common Mistakes:

• Not updating tail.next causing broken circular link
• Setting tail.next to null breaks circular list