> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/linked_list/circular-linked-list/insert-into-a-cyclic-sorted-list.md).

# Insert into a Cyclic Sorted List

## Question ([LI.599](http://www.lintcode.com/en/problem/insert-into-a-cyclic-sorted-list/#))

> 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

```java
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.