Insert into a Cyclic Sorted List

Question (LI.599)

Given a random node from a sorted circular linked list, insert a new value into a list and maintain the sorted property. Return the new node.

Node definition? Positive values only? No. Allow duplicates? Yes.

Example

I: 3->5->1->, 4
O: 3->4->5->1->

I: null, 5
O: 5->

I: 5->, 6
O: 5->6->

I: 5->6->1->, 0
O: 5->6->0->1->

Analysis

Normal case: insert when $val_{i-1} <= newval <= val_{i}$

Corner case: insert before start when new_val is min or max

Code

public ListNode insert(ListNode node, int value) {
    ListNode newNode = new ListNode(value);
    if (node == null) {
        newNode.next = newNode;
        return newNode;
    }
    ListNode start = findStart(node);
    ListNode prev = start, cur = start.next;
    while (cur != start) {
        if (prev.val <= value && value <= cur.val) {
            break;
        }
        prev = cur;
        cur = cur.next;
    }
    // insert new node
    prev.next = newNode;
    newNode.next = cur;
    return newNode;
}

// find the first smallest node in a CLL
private ListNode findStart(ListNode node) {
    ListNode prev = node, cur = node.next;    
    while (cur != node) {
        if (prev.val > cur.val) {
            break;
        }
        prev = cur; 
        cur = cur.next;
    }
    return cur;
}

Note: It is possible to write the solution in one iteration. Then the code has to check for the min/max case explicitly.