26. Insert in Sorted Circular Linked List

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

Given a sorted circular linked list, insert a new node containing a given data value into the list so that it remains a sorted circular linked list.

📘 Examples

Example 1:

Input:

head = 1→2→4 (circular), data = 2

Output:

1→2→2→4 (circular)

Explanation:

We insert the new node with 2 after the second node.

image

Example 2:

Input:

head = 1→4→7→9 (circular), data = 5

Output:

1→4→5→7→9 (circular)

Explanation:

We insert the new node with 5 after the node containing 4.

image

🔒 Constraints

• $2 ≤ number of nodes ≤ 10^6$

• $0 ≤ node->data ≤ 10^6$

• $0 ≤ data ≤ 10^6$

✅ My Approach

Gap Detection

We traverse the circular list looking for the proper "gap" between two consecutive nodes where the new data fits, taking into account the wrap‑around point (largest to smallest).

Algorithm Steps:

1. Create the new node n with n->data = data.

2. If head is null, make n->next = n and return n.

3. Use pointer cur = head.

4. Loop indefinitely:

   • Let nxt = cur->next.

   • Case 1: Normal gap: if cur->data ≤ data ≤ nxt->data, insert between cur and nxt.

   • Case 2: Wrap‑around gap: if cur->data > nxt->data (largest→smallest transition) and (data ≥ cur->data or data ≤ nxt->data), insert here.

   • Case 3: Full cycle fallback: if nxt == head, insert here.

   • On insertion: set cur->next = n, n->next = nxt.

   • If data < head->data, update head = n to maintain head as smallest.

   • Break the loop.

5. Return head.

🧮 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n), as in the worst case we traverse all nodes once to find the insertion point.

• Expected Auxiliary Space Complexity: O(1), since we use only a fixed number of pointers.

🧠 Code (C++)

class Solution {
  public:
    Node* sortedInsert(Node* head, int data) {
        Node* n = new Node(data);
        if (!head) {
            n->next = n;
            return n;
        }
        Node* cur = head;
        while (true) {
            Node* nxt = cur->next;
            if ((cur->data <= data && data <= nxt->data) ||
                (cur->data > nxt->data && (data >= cur->data || data <= nxt->data)) ||
                nxt == head) {
                cur->next = n;
                n->next = nxt;
                if (data < head->data) head = n;
                break;
            }
            cur = nxt;
        }
        return head;
    }
};

⚡ Alternative Approaches

📊 2️⃣ Linear Traversal with Do‑While Loop

Algorithm Steps:

1. Create new node n.

2. If head is null, link n to itself and return.

3. Set cur = head.

4. do-while loop until cur returns to head:

   • Let nxt = cur->next.

   • If (cur->data ≤ data ≤ nxt->data) or at wrap‑point (cur->data > nxt->data and (data ≥ cur->data or data ≤ nxt->data)), do:

     • cur->next = n; n->next = nxt;

     • If data < head->data then head = n.

     • Break.

   • cur = nxt.

5. Return head.

class Solution {
  public:
    Node* sortedInsert(Node* head, int data) {
        Node* n = new Node(data);
        if (!head) {
            n->next = n;
            return n;
        }
        Node* cur = head;
        do {
            Node* nxt = cur->next;
            if ((cur->data <= data && data <= nxt->data) ||
                (cur->data > nxt->data && (data >= cur->data || data <= nxt->data))) {
                cur->next = n;
                n->next = nxt;
                if (data < head->data) head = n;
                break;
            }
            cur = nxt;
        } while (cur != head);
        return head;
    }
};

✅ Why This Approach?

• Uses a clear do-while to guarantee at least one full cycle.

• Cleaner separation of traversal and insertion logic.

📝 Complexity Analysis:

• Time: 🔸 O(n) — one cycle maximum.

• Space: 🟢 O(1).

🪜 3️⃣ Find Maximum Node Then Insert

Algorithm Steps:

1. Traverse to find maxNode where maxNode->next == head or data decreases.

2. Start from maxNode->next (smallest), traverse until correct insert point (cur->data ≤ data ≤ cur->next->data).

3. If none found by maxNode, insert after maxNode.

4. Link new node and update head if needed.

class Solution {
  public:
    Node* sortedInsert(Node* head, int data) {
        Node* n = new Node(data);
        if (!head) { n->next = n; return n; }
        Node* maxNode = head;
        while (maxNode->next != head && maxNode->data <= maxNode->next->data)
            maxNode = maxNode->next;
        Node* cur = maxNode->next;
        while (cur != maxNode && !(cur->data <= data && data <= cur->next->data))
            cur = cur->next;
        if (cur == maxNode && !(cur->data <= data && data <= cur->next->data))
            cur = maxNode;
        n->next = cur->next;
        cur->next = n;
        if (data < head->data) head = n;
        return head;
    }
};

✅ Why This Approach?

• Explicitly handles the rotation point.

• Two-phase traversal: find boundary then insert.

📝 Complexity Analysis:

• Time: 🔸 O(n).

• Space: 🟢 O(1).

🔃 4️⃣ Break, Insert, Reconnect

Algorithm Steps:

1. Find tail node (where tail->next == head) and break the cycle (tail->next = nullptr).

2. Perform standard sorted insert on linear list.

3. Reconnect tail to the new head to restore circularity.

4. Return the new head.

class Solution {
  public:
    Node* sortedInsert(Node* head, int data) {
        Node* n = new Node(data);
        if (!head) { n->next = n; return n; }
        Node* tail = head;
        while (tail->next != head) tail = tail->next;
        tail->next = nullptr;

        if (data < head->data) {
            n->next = head;
            head = n;
        } else {
            Node* cur = head;
            while (cur->next && cur->next->data < data) cur = cur->next;
            n->next = cur->next;
            cur->next = n;
        }

        tail = head;
        while (tail->next) tail = tail->next;
        tail->next = head;
        return head;
    }
};

✅ Why This Works:

• Leverages familiar linear list insert.

• Easy to debug by isolating circular logic.

📝 Complexity Analysis:

• Time: 🔸 O(n).

• Space: 🟢 O(1).

🆚 Comparison of Approaches

Approach	⏱️ Time	🗂️ Space	✅ Pros	⚠️ Cons
▶️ Gap Detection (main)	🟢 O(n)	🟢 O(1)	Elegant, single pass handles all edge cases	Condition‑heavy logic
🔁 Do‑While Traversal	🔸 O(n)	🟢 O(1)	Guaranteed cycle, clear syntax	Slightly more verbose
🪜 Max Node First	🔸 O(n)	🟢 O(1)	Separates boundary detection from insertion	Two traversal phases
🔃 Break → Insert → Reconnect	🔸 O(n)	🟢 O(1)	Simplifies to linear insert + reconnect	Modifies structure temporarily

✅ Best Choice by Scenario

Scenario	Recommended Approach
🔁 Want concise, all‑in‑one detection/insert	🥇 Gap Detection
🔧 Prefer explicit loop control	🥈 Do‑While Traversal
🧪 Need clear boundary then insertion logic	🥉 Max Node First
🪛 Familiar with linear inserts	🔹 Break → Insert → Reconnect

🧑‍💻 Code (Java)

class Solution {
    public Node sortedInsert(Node head, int data) {
        Node n = new Node(data);
        if (head == null) {
            n.next = n;
            return n;
        }
        Node cur = head;
        while (true) {
            if ((cur.data <= data && cur.next.data >= data) ||
                (cur.data > cur.next.data && (data >= cur.data || data <= cur.next.data)) ||
                cur.next == head) {
                n.next = cur.next;
                cur.next = n;
                if (data < head.data) head = n;
                break;
            }
            cur = cur.next;
        }
        return head;
    }
}

🐍 Code (Python)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Solution:
    def sortedInsert(self, head, data):
        n = Node(data)
        if not head:
            n.next = n
            return n
        cur = head
        while True:
            if (cur.data <= data <= cur.next.data or
                cur.data > cur.next.data and (data >= cur.data or data <= cur.next.data) or
                cur.next == head):
                n.next = cur.next
                cur.next = n
                if data < head.data:
                    head = n
                break
            cur = cur.next
        return head

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count