Deletion from a Circular Linked List

Problem Statement

Given a circular linked list and a key, delete the node containing the given key from the circular linked list. If the key is not found, return the original list. Handle all cases including deletion of head node, tail node, and middle node.

Example

Input: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 1), key = 3
Output: 1 -> 2 -> 4 -> 5 -> (back to 1)

Input: 1 -> 2 -> 3 -> (back to 1), key = 1
Output: 2 -> 3 -> (back to 2)

Brute Force Approach

Intuition

The brute force approach involves traversing the circular linked list to find the node to be deleted. We need to handle three cases:

Deletion of the head node
Deletion of a middle node
Deletion of the last node (whose next points to head)

For each case, we traverse the list to find the node and its previous node, then update the pointers accordingly.

Algorithm

If the list is empty, return null
If there's only one node and it matches the key, delete it and return null
If the head contains the key, find the last node, update its next to head's next, and delete head
Otherwise, traverse to find the node with the key and its previous node
Update the previous node's next pointer to skip the node to be deleted

Code

java

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    public static Node deleteNode(Node head, int key) {
        if (head == null) return null;
        
        // Single node case
        if (head.next == head && head.data == key) {
            return null;
        }
        
        // Find the last node
        Node last = head;
        while (last.next != head) {
            last = last.next;
        }
        
        // If head needs to be deleted
        if (head.data == key) {
            last.next = head.next;
            return head.next;
        }
        
        // Search for the node to delete
        Node curr = head;
        Node prev = null;
        
        do {
            prev = curr;
            curr = curr.next;
            if (curr.data == key) {
                prev.next = curr.next;
                return head;
            }
        } while (curr != head);
        
        // Key not found
        return head;
    }
    
    public static void printList(Node head) {
        if (head == null) {
            System.out.println("Empty list");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(back to " + head.data + ")");
    }
}

Complexity Analysis

Time Complexity: O(n) - We may need to traverse the entire list to find the node
Space Complexity: O(1) - Only using constant extra space

Optimal Approach

Intuition

The optimal approach is essentially the same as brute force for this problem since we must traverse to find both the node to delete and potentially the last node. However, we can optimize by combining the search for the last node with the search for the node to delete in a single pass when possible.

Algorithm

Handle edge cases (empty list, single node)
If deleting head, copy next node's data to head and delete next node (if not single node)
For other nodes, traverse once to find and delete
Use a single traversal to handle all cases efficiently

Code

java

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedListOptimal {
    public static Node deleteNodeOptimal(Node head, int key) {
        if (head == null) return null;
        
        // Single node case
        if (head.next == head) {
            if (head.data == key) {
                return null;
            }
            return head;
        }
        
        // If head needs to be deleted - copy next node's data
        if (head.data == key) {
            Node temp = head.next;
            head.data = temp.data;
            head.next = temp.next;
            return head;
        }
        
        // Search for the node to delete
        Node curr = head;
        while (curr.next != head && curr.next.data != key) {
            curr = curr.next;
        }
        
        // If found
        if (curr.next.data == key) {
            curr.next = curr.next.next;
        }
        
        return head;
    }
    
    public static void printList(Node head) {
        if (head == null) {
            System.out.println("Empty list");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(back to " + head.data + ")");
    }
}

Complexity Analysis

Time Complexity: O(n) - Single traversal in the worst case
Space Complexity: O(1) - Only using constant extra space

Key Takeaways

Circular Structure Handling: The main challenge is handling the circular nature - the last node points back to the head
Head Deletion: Deleting the head node requires special handling - either update the last node's pointer or use the copy technique
Copy Technique: Instead of actually deleting the head, we can copy the next node's data to head and delete the next node
Single Node Edge Case: Always handle the case when there's only one node in the circular list
Termination Condition: Use do-while loops or track the starting point to ensure proper termination when traversing circular lists