Delete a Node from Circular Linked List in DSA C++ - 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, we must update the last node's next pointer if the head is deleted, to keep the circle intact.

intermediate

What steps do you follow to delete a node with a given value from a circular linked list?

1. Find the node to delete and its previous node.
2. If node is head, update head and last node's next.
3. Change previous node's next to node's next.
4. Delete the node.

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 nullptr in C++).

advanced

Show the C++ code snippet to delete a node with a given key from a circular linked list.

```cpp void deleteNode(Node*& head, int key) { if (!head) return; Node *curr = head, *prev = nullptr; while (curr->data != key) { if (curr->next == head) return; // key not found prev = curr; curr = curr->next; } if (curr == head && curr->next == head) { delete curr; head = nullptr; return; } if (curr == head) { prev = head; while (prev->next != head) prev = prev->next; head = head->next; prev->next = head; delete curr; } else { prev->next = curr->next; delete curr; } } ```

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

A Itself

B Null

C The first node

D The previous node

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

What must you update when deleting the head node in a circular linked list?

A Only the head pointer

B The last node's next pointer and the head pointer

C Only the last node's next pointer

D No pointers need updating

When deleting the head, you must update the head pointer and also the last node's next pointer to the new head.

If the circular linked list has only one node and you delete it, what should the head be set to?

A Null (nullptr)

B The deleted node

C It remains the same

D The next node

Deleting the only node empties the list, so head should be set to null (nullptr).

What happens if the key to delete is not found in the circular linked list?

A Delete the head node

B Delete the last node

C Delete a random node

D Do nothing

If the key is not found, no deletion happens and the list remains unchanged.

Which pointer do you need to keep track of to delete a node in a circular linked list?

A The current node and its previous node

B Only the head node

C Only the current node

D Only the last node

You need both the current node and its previous node to update links correctly when deleting.

Explain the process of deleting a node from a circular linked list, including special cases.

Think about how the last node's next pointer must change if the head is deleted.

Write the key steps in C++ to delete a node with a given value from a circular linked list.

Remember to keep the list circular after deletion.

Practice

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

easy

A. The list becomes empty (head points to null).

B. The list still contains one node pointing to itself.

C. The list becomes a linear linked list.

D. The list throws an error and stops.

Solution

1. Step 1: Understand single-node circular list

   A circular linked list with one node points to itself.

2. Step 2: Delete the only node

   Removing this node leaves no nodes, so head becomes null.

3. Final Answer:

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

4. Quick Check:

   Single node deleted = empty list [OK]

Hint: Deleting last node empties list, head = null [OK]

Common Mistakes:

• Assuming list still has one node after deletion
• Not updating head to null
• Confusing circular with linear list after deletion

2. Which of the following is the correct syntax to delete a node with value key from a circular linked list in C++?

easy

A. void deleteNode(Node head, int key) { /* code */ }

B. void deleteNode(Node* head, int key) { /* code */ }

C. void deleteNode(Node*& head, int key) { /* code */ }

D. void deleteNode(int key, Node* head) { /* code */ }

Solution

1. Step 1: Understand pointer passing in C++

   To modify the head pointer itself, pass it by reference (Node*& head).

2. Step 2: Check parameter order and types

   Function should accept head reference first, then key to delete.

3. Final Answer:

   void deleteNode(Node*& head, int key) { /* code */ } -> Option C

4. Quick Check:

   Pass head by reference to modify it [OK]

Hint: Pass head as reference to update list head [OK]

Common Mistakes:

• Passing head by value (won't update original list)
• Wrong parameter order
• Passing head as object, not pointer or reference

3. Given the circular linked list: 10 -> 20 -> 30 -> (back to 10), what is the list after deleting node with value 20?

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

   Node with value 20 is between 10 and 30.

2. Step 2: Remove node 20 and link 10 to 30

   Update 10's next pointer to 30, maintaining circular link.

3. Final Answer:

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

4. Quick Check:

   Deleted 20, linked 10 to 30 [OK]

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

Common Mistakes:

• Not updating previous node's next pointer
• Breaking circular link
• Deleting wrong node

4. What is wrong with this code snippet for deleting a node from a circular linked list?

void deleteNode(Node*& head, int key) {
  if (!head) return;
  Node* curr = head;
  while (curr->next != head && curr->next->data != key) {
    curr = curr->next;
  }
  if (curr->next->data == key) {
    Node* temp = curr->next;
    curr->next = temp->next;
    delete temp;
  }
}

medium

A. Does not handle deleting the head node correctly.

B. Does not check if list is empty.

C. Deletes node without updating pointers.

D. Infinite loop due to wrong while condition.

Solution

1. Step 1: Analyze deletion logic

   Code searches for node before target and deletes next node.

2. Step 2: Check head deletion case

   If node to delete is head, head pointer is not updated, causing errors.

3. Final Answer:

   Does not handle deleting the head node correctly. -> Option A

4. Quick Check:

   Head deletion needs special handling [OK]

Hint: Update head if deleted node is head [OK]

Common Mistakes:

• Ignoring head node deletion
• Not updating head pointer
• Assuming node always exists

5. You have a circular linked list: 5 -> 15 -> 25 -> 35 -> (back to 5). You want to delete the node with value 5 (head node). Which steps correctly update the list?

hard

A. Swap head data with next node and delete next node.

B. Delete head node directly without updating last node's next.

C. Set head to null without deleting any node.

D. Find last node (35), set its next to head's next (15), update head to 15.

Solution

1. Step 1: Locate last node

   Traverse list to find node pointing to head (value 35).

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

   Set last node's next to head's next (node with value 15).

3. Step 3: Update head pointer

   Set head to head's next (15) to maintain circular list.

4. Final Answer:

   Find last node (35), set its next to head's next (15), update head to 15. -> Option D

5. Quick Check:

   Update last node and head to delete head node [OK]

Hint: Update last node's next and head to delete head [OK]

Common Mistakes:

• Not updating last node's next pointer
• Not updating head pointer
• Deleting head without fixing links