Insert into a Sorted Circular Linked List
Insert a value into a sorted circular list at the correct position, handling wrap-around and uniform-value cases.
4 min read
linked-list
Problem#
Given a node in a sorted circular linked list (any node), insert a new value preserving sortedness. Return any node of the modified list (must include the new node).
Examples#
head = [3,4,1] with cycle, insertVal = 2→[3,4,1,2]head = null, insertVal = 1→[1](self-loop)
Constraints#
0 <= n <= 5 * 10^4.
Hints#
Hint 1
Three insertion conditions: between two sorted neighbors; at the wrap-around between max and min; uniform-value lap.
Approach#
Walk one full lap. Insert when:
curr <= val <= next(normal slot)curr > next(the wrap-around) andval >= curr || val <= next(val belongs at the boundary)- We completed a full lap with no insertion (every value equals the others) — insert anywhere.
Solution#
class Solution {public: Node* insert(Node* head, int insertVal) { Node* node = new Node(insertVal); if (!head) { node->next = node; return node; } Node *curr = head; do { Node* nxt = curr->next; if ((curr->val <= insertVal && insertVal <= nxt->val) || (curr->val > nxt->val && (insertVal >= curr->val || insertVal <= nxt->val))) { curr->next = node; node->next = nxt; return head; } curr = nxt; } while (curr != head); // Uniform-value list — insert anywhere. node->next = head->next; head->next = node; return head; }};func insert(head *Node, insertVal int) *Node { node := &Node{Val: insertVal} if head == nil { node.Next = node return node } curr := head for { nxt := curr.Next if (curr.Val <= insertVal && insertVal <= nxt.Val) || (curr.Val > nxt.Val && (insertVal >= curr.Val || insertVal <= nxt.Val)) { curr.Next = node node.Next = nxt return head } curr = nxt if curr == head { break } } node.Next = head.Next head.Next = node return head}class Solution: def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node': node = Node(insertVal) if not head: node.next = node return node curr = head while True: nxt = curr.next if (curr.val <= insertVal <= nxt.val) or \ (curr.val > nxt.val and (insertVal >= curr.val or insertVal <= nxt.val)): curr.next = node node.next = nxt return head curr = nxt if curr == head: break node.next = head.next head.next = node return headfunction insert(head, insertVal) { const node = new Node(insertVal); if (!head) { node.next = node; return node; } let curr = head; do { const nxt = curr.next; if ((curr.val <= insertVal && insertVal <= nxt.val) || (curr.val > nxt.val && (insertVal >= curr.val || insertVal <= nxt.val))) { curr.next = node; node.next = nxt; return head; } curr = nxt; } while (curr !== head); // Uniform-value list — insert anywhere. node.next = head.next; head.next = node; return head;}class Solution { public Node insert(Node head, int insertVal) { Node node = new Node(insertVal); if (head == null) { node.next = node; return node; } Node curr = head; do { Node nxt = curr.next; if ((curr.val <= insertVal && insertVal <= nxt.val) || (curr.val > nxt.val && (insertVal >= curr.val || insertVal <= nxt.val))) { curr.next = node; node.next = nxt; return head; } curr = nxt; } while (curr != head); // Uniform-value list — insert anywhere. node.next = head.next; head.next = node; return head; }}function insert(head: Node | null, insertVal: number): Node { const node = new Node(insertVal); if (!head) { node.next = node; return node; } let curr: Node = head; do { const nxt = curr.next!; if ((curr.val <= insertVal && insertVal <= nxt.val) || (curr.val > nxt.val && (insertVal >= curr.val || insertVal <= nxt.val))) { curr.next = node; node.next = nxt; return head; } curr = nxt; } while (curr !== head); // Uniform-value list — insert anywhere. node.next = head.next; head.next = node; return head;}Editorial#
Three cases is exactly right. The wrap-around predicate handles values smaller than the minimum and larger than the maximum (they both belong at the boundary). The fallback after the do-while handles the all-equal degenerate case — we walked the entire cycle and never found a “between two values” slot.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#