Insert into a Sorted Circular Linked List

medium linked list

Problem

Insert val into a sorted circular singly linked list. The list may be empty.

Inputlist circular: 3→4→1→3 ; insert 2

Output3→4→1→2→3

Wraps around if needed.

input

def insert(head, val):
    node = Node(val)
    if not head: node.next = node; return node
    p = head
    while True:
        if p.val <= val <= p.next.val: break
        if p.val > p.next.val and (val >= p.val or val <= p.next.val): break
        p = p.next
        if p == head: break
    node.next = p.next; p.next = node; return head

function insert(head, val) {
  const node = new Node(val);
  if (!head) { node.next = node; return node; }
  let p = head;
  do {
    if (p.val <= val && val <= p.next.val) break;
    if (p.val > p.next.val && (val >= p.val || val <= p.next.val)) break;
    p = p.next;
  } while (p !== head);
  node.next = p.next; p.next = node;
  return head;
}

Node insert(Node head, int val) {
    Node node = new Node(val);
    if (head == null) { node.next = node; return node; }
    Node p = head;
    do {
        if (p.val <= val && val <= p.next.val) break;
        if (p.val > p.next.val && (val >= p.val || val <= p.next.val)) break;
        p = p.next;
    } while (p != head);
    node.next = p.next; p.next = node;
    return head;
}

Node* insert(Node* head, int val) {
    Node* node = new Node(val);
    if (!head) { node->next = node; return node; }
    Node* p = head;
    do {
        if (p->val <= val && val <= p->next->val) break;
        if (p->val > p->next->val && (val >= p->val || val <= p->next->val)) break;
        p = p->next;
    } while (p != head);
    node->next = p->next; p->next = node;
    return head;
}

Explanation

This is a sorted list that loops back on itself, so there is no real "end" to stop at. The idea is to walk around the circle at most once and drop the new value into the first place where it fits between a node p and its neighbor p.next.

There are three situations to handle. First, an empty list: we make the new node point to itself with node.next = node and return it. Second, the normal case: the value belongs between two nodes when p.val <= val <= p.next.val — a plain ascending gap.

The tricky case is the wrap point, where the largest value connects back to the smallest (like 4 → 1). We detect it with p.val > p.next.val. At that single seam, any value that is bigger than the max (val >= p.val) or smaller than the min (val <= p.next.val) belongs there. This is how new maximums and minimums get placed.

Once we find the spot, we splice the node in with node.next = p.next; p.next = node. If we loop all the way back to head without finding a fit (all values equal), we just insert wherever we stopped.

Example: circular 3 → 4 → 1 → 3, inserting 2. At p = 1, p.next = 3 and 1 <= 2 <= 3 holds, so we splice between them to get 3 → 4 → 1 → 2 → 3.

Time: O(n) Space: O(1)