Insert into a Sorted Circular List — Pointer Scan

Problem 240 · Insert into a Sorted Circular List

Difficulty: Medium · Pattern: Circular List Pointer Scan

Cases to Handle

Normal: find where cur.val ≤ val ≤ cur.next.val
Wraparound: cur.val > cur.next.val (at the seam) and val is max or min
Full traversal without match: all equal, insert anywhere

Solutions

# Python
def insert(head, insertVal):
    node = Node(insertVal)
    if not head: node.next = node; return node
    cur = head
    while True:
        if cur.val <= insertVal <= cur.next.val:
            break
        if cur.val > cur.next.val:  # at seam
            if insertVal >= cur.val or insertVal <= cur.next.val:
                break
        if cur.next == head:  # full loop
            break
        cur = cur.next
    node.next = cur.next; cur.next = node
    return head

// Java
public Node insert(Node head, int insertVal) {
    Node node = new Node(insertVal);
    if (head == null) { node.next = node; return node; }
    Node cur = head;
    while (true) {
        if (cur.val <= insertVal && insertVal <= cur.next.val) break;
        if (cur.val > cur.next.val && (insertVal >= cur.val || insertVal <= cur.next.val)) break;
        if (cur.next == head) break;
        cur = cur.next;
    }
    node.next = cur.next; cur.next = node;
    return head;
}

Complexity

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