# LeetCode 708: Insert into a Sorted Circular Linked List

## Problem Restatement

We are given a node from a sorted circular linked list.

The list is sorted in non-decreasing order, but the given node may be any node in the list. It is not necessarily the smallest node.

We are also given an integer:

```python
insertVal
```

We need to insert a new node with value `insertVal` into the circular linked list so that the list remains sorted.

If the list is empty, we create a new node that points to itself.

Return the original given node if the list was not empty. Return the new node if the list was empty.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head`, a reference to any node in a sorted circular linked list |
| Input | `insertVal`, the value to insert |
| Output | A node reference to the circular list after insertion |
| Empty list | Create one node pointing to itself |
| Important detail | `head` may not be the smallest node |

The function shape is:

```python
class Solution:
    def insert(self, head: "Optional[Node]", insertVal: int) -> "Node":
        ...
```

## Examples

Example 1:

```python
head = [3, 4, 1]
insertVal = 2
```

The list is circular.

Its sorted order is:

```python
1 -> 3 -> 4 -> back to 1
```

The given `head` points to the node with value `3`.

The value `2` belongs between `1` and `3`.

After insertion, one valid circular order from the given head is:

```python
[3, 4, 1, 2]
```

Example 2:

```python
head = []
insertVal = 1
```

The list is empty.

Create one node:

```python
1 -> back to 1
```

Return that new node.

Example 3:

```python
head = [1]
insertVal = 0
```

The list has one node.

After insertion:

```python
1 -> 0 -> back to 1
```

This is valid because the circular sorted order is:

```python
0 -> 1 -> back to 0
```

## First Thought: Find the Smallest Node

One possible approach is to first find the smallest node in the circular list.

Then we could treat the list as if it starts at the smallest value, scan forward, and insert `insertVal` in the usual sorted position.

This works, but it is not necessary.

We can insert while walking from the given `head`. We only need to inspect adjacent pairs of nodes.

## Key Insight

When walking around a sorted circular linked list, there are two useful kinds of adjacent pairs.

The first kind is a normal increasing pair:

```python
prev.val <= curr.val
```

In this case, we can insert between them if:

```python
prev.val <= insertVal <= curr.val
```

The second kind is the rotation boundary:

```python
prev.val > curr.val
```

This is where the largest value points back to the smallest value.

For example:

```python
3 -> 4 -> 1 -> back to 3
```

The pair `4 -> 1` is the boundary.

At this boundary, we can insert if `insertVal` is larger than or equal to the maximum, or smaller than or equal to the minimum:

```python
insertVal >= prev.val or insertVal <= curr.val
```

There is also one special case: all nodes may have the same value.

For example:

```python
3 -> 3 -> 3 -> back to 3
```

If `insertVal = 4`, no normal gap or boundary condition will match. After one full loop, we can insert anywhere.

## Algorithm

Handle the empty list first.

If `head is None`:

1. Create a new node.
2. Point it to itself.
3. Return it.

Otherwise:

1. Set `prev = head`.
2. Set `curr = head.next`.
3. Walk around the circular list.
4. For each pair `prev -> curr`, check whether one of these is true:
   - `prev.val <= insertVal <= curr.val`
   - `prev.val > curr.val` and `insertVal >= prev.val`
   - `prev.val > curr.val` and `insertVal <= curr.val`
5. If a valid place is found, stop.
6. If we return to `head`, stop anyway and insert there.
7. Create the new node between `prev` and `curr`.

## Correctness

If the list is empty, the algorithm creates one node whose `next` pointer points to itself. This is a valid sorted circular linked list containing exactly `insertVal`.

Now assume the list is not empty.

The algorithm checks each adjacent pair `prev -> curr` around the circle.

If `prev.val <= insertVal <= curr.val`, inserting between `prev` and `curr` preserves the local sorted order. The rest of the circular list is unchanged, so the full circular sorted order remains valid.

If `prev.val > curr.val`, the pair is the rotation boundary where the largest value points to the smallest value. At this location, values greater than or equal to the maximum and values smaller than or equal to the minimum both belong. Therefore inserting `insertVal` there is correct when `insertVal >= prev.val` or `insertVal <= curr.val`.

If neither condition is found after one full loop, then no adjacent pair separates `insertVal`. This happens when all existing node values are equal, or when every location is equally valid. Inserting anywhere preserves the circular sorted order.

The algorithm inserts exactly one new node by setting:

```python
prev.next = new_node
new_node.next = curr
```

So the list remains circular, contains all old nodes, and includes the new value.

## Complexity

Let `n` be the number of nodes in the circular list.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We may scan one full circle |
| Space | `O(1)` | We only use a few pointers |

## Implementation

```python
# Definition for a Node.
# class Node:
#     def __init__(self, val=None, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def insert(self, head: "Optional[Node]", insertVal: int) -> "Node":
        new_node = Node(insertVal)

        if head is None:
            new_node.next = new_node
            return new_node

        prev = head
        curr = head.next

        while True:
            normal_place = prev.val <= insertVal <= curr.val

            boundary_place = (
                prev.val > curr.val
                and (insertVal >= prev.val or insertVal <= curr.val)
            )

            if normal_place or boundary_place:
                break

            prev = curr
            curr = curr.next

            if prev == head:
                break

        prev.next = new_node
        new_node.next = curr

        return head
```

## Code Explanation

We create the node first:

```python
new_node = Node(insertVal)
```

If the input list is empty, the new node must point to itself:

```python
if head is None:
    new_node.next = new_node
    return new_node
```

For a non-empty list, we walk through adjacent pairs:

```python
prev = head
curr = head.next
```

The normal insertion case checks whether the new value fits between two increasing values:

```python
normal_place = prev.val <= insertVal <= curr.val
```

The boundary case checks whether we are at the max-to-min transition:

```python
boundary_place = (
    prev.val > curr.val
    and (insertVal >= prev.val or insertVal <= curr.val)
)
```

If either condition is true, we found the insertion position:

```python
if normal_place or boundary_place:
    break
```

Otherwise, move forward:

```python
prev = curr
curr = curr.next
```

If we return to the starting node, we have checked the whole circle:

```python
if prev == head:
    break
```

Then we insert the new node between `prev` and `curr`:

```python
prev.next = new_node
new_node.next = curr
```

Finally, return the original head:

```python
return head
```

## Testing

For local testing, we can convert part of the circular list into a normal Python list.

Since the list is circular, we must stop after a known number of nodes.

```python
class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

def build_circular(values):
    if not values:
        return None

    nodes = [Node(value) for value in values]

    for i in range(len(nodes)):
        nodes[i].next = nodes[(i + 1) % len(nodes)]

    return nodes[0]

def circular_to_list(head, count):
    values = []
    cur = head

    for _ in range(count):
        values.append(cur.val)
        cur = cur.next

    return values

def is_circular_sorted(head, count):
    values = circular_to_list(head, count)

    drops = 0

    for i in range(count):
        if values[i] > values[(i + 1) % count]:
            drops += 1

    return drops <= 1

def test_insert_sorted_circular_list():
    s = Solution()

    head = build_circular([3, 4, 1])
    result = s.insert(head, 2)

    assert result is head
    assert is_circular_sorted(result, 4)

    result = s.insert(None, 1)

    assert circular_to_list(result, 1) == [1]
    assert result.next is result

    head = build_circular([1])
    result = s.insert(head, 0)

    assert result is head
    assert is_circular_sorted(result, 2)

    head = build_circular([3, 3, 3])
    result = s.insert(head, 4)

    assert result is head
    assert is_circular_sorted(result, 4)

    head = build_circular([1, 3, 5])
    result = s.insert(head, 4)

    assert result is head
    assert is_circular_sorted(result, 4)

    print("all tests passed")

test_insert_sorted_circular_list()
```

Test coverage:

| Test | Why |
|---|---|
| Insert between min and head | Confirms boundary traversal works |
| Empty list | Confirms self-cycle creation |
| Single node | Confirms circular insertion with one old node |
| All equal values | Confirms full-loop fallback |
| Insert in normal increasing gap | Confirms ordinary sorted insertion |