Delete a Node from Circular Linked List in DSA C++

Mental Model

A circular linked list loops back to the start, so deleting a node means adjusting pointers without breaking the loop.

Analogy: Imagine people sitting in a circle holding hands. Removing one person means the two neighbors hold hands directly, keeping the circle unbroken.

head -> 1 -> 2 -> 3 -> 4 -> back to head (1)
          ↑__________________________↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 (circular), delete node with value 3

Goal: Remove the node with value 3 and keep the list circular

Step 1: start at head (1), look for node with value 3

head -> [1] -> 2 -> 3 -> 4 -> back to head (1)

Why: We need to find the node before the one to delete to adjust pointers

Step 2: move to next node (2), check if next node is 3

head -> 1 -> [2] -> 3 -> 4 -> back to head (1)

Why: Check if next node is the target to delete

Step 3: next node is 3, adjust 2's next pointer to 4, skipping 3

head -> 1 -> 2 -> [4] -> back to head (1)

Why: By skipping node 3, we remove it from the circle

Step 4: delete node 3 and confirm circular link intact

head -> 1 -> 2 -> 4 -> back to head (1)

Why: The circle remains unbroken after deletion

Result:

head -> 1 -> 2 -> 4 -> back to head (1)

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class CircularLinkedList {
public:
    Node* head;
    CircularLinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            newNode->next = head; // point to itself
            return;
        }
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next; // move to last node
        }
        temp->next = newNode;
        newNode->next = head; // maintain circular link
    }

    void deleteNode(int key) {
        if (!head) return; // empty list

        Node *curr = head, *prev = nullptr;

        // If head is to be deleted and only one node
        if (head->data == key && head->next == head) {
            delete head;
            head = nullptr;
            return;
        }

        // If head is to be deleted and more than one node
        if (head->data == key) {
            // find last node to update its next
            Node* last = head;
            while (last->next != head) {
                last = last->next; // find last node
            }
            last->next = head->next; // last points to second node
            Node* temp = head;
            head = head->next; // update head
            delete temp; // delete old head
            return;
        }

        // For other nodes
        prev = head;
        curr = head->next;
        while (curr != head && curr->data != key) {
            prev = curr;
            curr = curr->next; // move forward
        }

        if (curr != head && curr->data == key) {
            prev->next = curr->next; // unlink node
            delete curr; // delete node
        }
    }

    void printList() {
        if (!head) {
            cout << "List is empty\n";
            return;
        }
        Node* temp = head;
        do {
            cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != head);
        cout << "back to head (" << head->data << ")\n";
    }
};

int main() {
    CircularLinkedList cll;
    cll.append(1);
    cll.append(2);
    cll.append(3);
    cll.append(4);

    cout << "Original list:\n";
    cll.printList();

    cll.deleteNode(3);

    cout << "After deleting 3:\n";
    cll.printList();

    return 0;
}

while (temp->next != head) { temp = temp->next; }

advance temp to last node to append new node

if (head->data == key && head->next == head) { delete head; head = nullptr; return; }

handle deletion when only one node matches key

if (head->data == key) { while (last->next != head) { last = last->next; } last->next = head->next; head = head->next; delete temp; return; }

handle deletion of head node and update last node's next pointer

while (curr != head && curr->data != key) { prev = curr; curr = curr->next; }

search for node with key to delete

if (curr != head && curr->data == key) { prev->next = curr->next; delete curr; }

unlink and delete the found node

Output

Original list:

1 -> 2 -> 3 -> 4 -> back to head (1)

After deleting 3:

1 -> 2 -> 4 -> back to head (1)

Complexity Analysis

Time: O(n) because in worst case we traverse all nodes once to find the node to delete

Space: O(1) because we only use a few pointers regardless of list size

vs Alternative: Compared to singly linked list deletion, circular list requires careful pointer updates to maintain the loop, but time complexity remains similar

Edge Cases

empty list

deleteNode returns immediately without changes

DSA C++

if (!head) return;

single node list where node matches key

node is deleted and list becomes empty

DSA C++

if (head->data == key && head->next == head) { delete head; head = nullptr; return; }

deleting head node in multi-node list

head pointer updates and last node's next pointer updates to new head

DSA C++

if (head->data == key) { ... }

key not found in list

list remains unchanged

DSA C++

while (curr != head && curr->data != key) { ... }

When to Use This Pattern

When you see a problem asking to remove an element from a circular linked list, use pointer updates carefully to maintain the circular link without breaking the loop.

Common Mistakes

Mistake: Not updating the last node's next pointer when deleting the head node
Fix: Find the last node and update its next pointer to the new head before deleting the old head

Mistake: Not handling the single-node list deletion case
Fix: Check if head points to itself and delete properly, setting head to nullptr

Summary

Deletes a node with a given value from a circular linked list while keeping the list circular.

Use when you need to remove elements from a circular linked list without breaking its loop structure.

The key insight is to carefully update pointers, especially the last node's next pointer, to maintain the circular link.

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