Insert in Sorted Circular Linked List

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Insert a value into sorted circular linked list maintaining order.

Algorithm

1Find insertion point: node where curr.val <= val <= curr.next.val. Or at wrap-around point.
2Handle: empty list, value less than min, value greater than max (insert at wrap).

Common Pitfalls

•Three cases: normal insertion, insert at boundary (new max or new min), empty list. Same as LC 708.

Insert in Sorted Circular Linked List.java

Java

// Approach: Traverse to find the correct insertion point considering wrap-around cases.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }
}

class Solution {
    public Node sortedInsert(Node head, int data) {
        Node prev = null;
        Node curr = head;

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

        while (curr.data < data) {
            curr = curr.next;
            prev = prev.next;

            if (curr == head)
                break;
        }

        Node newNode = new Node(data);
        prev.next = newNode;
        newNode.next = curr;

        if (head.data > data)
            return newNode;
        else
            return head;
    }
}

Was this solution helpful?