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:

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

The function shape is:

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

Examples

Example 1:

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

The list is circular.

Its sorted order is:

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:

[3, 4, 1, 2]

Example 2:

head = []
insertVal = 1

The list is empty.

Create one node:

1 -> back to 1

Return that new node.

Example 3:

head = [1]
insertVal = 0

The list has one node.

After insertion:

1 -> 0 -> back to 1

This is valid because the circular sorted order is:

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:

prev.val <= curr.val

In this case, we can insert between them if:

prev.val <= insertVal <= curr.val

The second kind is the rotation boundary:

prev.val > curr.val

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

For example:

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:

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

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

For example:

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:

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.

Implementation

# 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:

new_node = Node(insertVal)

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

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

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

prev = head
curr = head.next

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

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

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

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

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

if normal_place or boundary_place:
    break

Otherwise, move forward:

prev = curr
curr = curr.next

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

if prev == head:
    break

Then we insert the new node between prev and curr:

prev.next = new_node
new_node.next = curr

Finally, return the original head:

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.

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: