Deletion and Reverse in Circular Linked List

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Delete a node from and reverse a circular linked list.

Algorithm

1Delete: find node before target (traverse until next == target). Relink to skip target.
2Reverse: standard linked list reverse but reconnect last node to new head.

Common Pitfalls

•Circular: tail.next == head. On deletion: traverse the full circle to find predecessor. On reverse: fix the circularity after reversal.

Deletion and Reverse in Circular Linked List.java

Java

// Approach: Handle deletion with pointer adjustment for circular structure; reverse by relinking all nodes.
// Time: O(n) Space: O(1)
class Solution {
    // Function to reverse a circular linked list
    Node reverse(Node head) {
        if (head == null)
            return head;

        Node prev = null;
        Node cur = head;
        Node nex = head;

        do {
            nex = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nex;
        } while (cur != head);

        head.next = prev;
        return head = prev;
    }

    // Function to delete a node from the circular linked list
    Node deleteNode(Node head, int key) {
        if (head == null)
            return head;
            
        Node prev = null;
        Node cur = head;

        do {
            if (cur.data == key) {
                if (prev == null) {
                    Node temp = head;
                    do {
                        temp = temp.next;
                    } while (temp.next != head);
                    temp.next = head.next;
                    return head = head.next;
                } else {
                    prev.next = cur.next;
                    return head;
                }
            }
            prev = cur;
            cur = cur.next;
        } while (cur != head);
        return head;
    }
}

Was this solution helpful?