Insert into a Sorted Circular Linked List

Table of Contents +

Insert into a Sorted Circular Linked List looks small. But it is full of corner cases. A circular list has no clear end, so the wrap-around point is easy to get wrong. The interviewer wants to see if you can handle every case cleanly without a crash.

🎯 The Problem

You must drop a new value into a circular list and keep it sorted. Here are the rules.

A circular linked list is a chain where the last node points back to the first, not to nothing.
A sorted circular list goes in increasing order, then wraps from the largest value back to the smallest.
You get a pointer to any node in the list, plus a value to insert.
Place a new node so the list stays sorted.
Return a pointer to any node in the list.

Input:  list = 3 -> 4 -> 1 -> (back to 3),  insert = 2
Output: 3 -> 4 -> 1 -> 2 -> (back to 3)

Reading in sorted order from the smallest: 1 -> 2 -> 3 -> 4

The new value 2 belongs between 1 and 3. So we splice it in there, and the circle stays sorted.

Here is the list before the insert. Notice the last node loops back to the first.

🧩 The Cases to Handle

This problem is really about cases, not speed. Here is each one.

Normal: the value fits between two neighbors. Find a node cur where cur.val <= insert <= cur.next.val, then splice between cur and cur.next.
Wrap seam: the largest value points back to the smallest, so cur.val > cur.next.val. A new maximum or a new minimum belongs right here.
All equal: every node has the same value. No comparison ever fits, so after one full loop drop the node anywhere.
Empty: the given pointer is null. Make one node that points to itself.

This is the decision flow for where the new node goes.

🐢 Approach 1: Gather, Sort, Rebuild (Brute Force)

The idea in one line: pull every value into an array, add the new one, sort, then build a fresh circle.

The idea:

Walk the circle once and copy all values into an array.
Add the new value to that array.
Sort the array, then build a new sorted circular list from it.

Why it is weak:

Sorting costs O(n log n). The list was already sorted, so this wastes that.
It builds a whole new list and uses O(n) extra memory.
The problem only wants one node added, so this is far more work than needed.

Here is the gather-sort-rebuild code:

def insert(head, insertVal):
    if not head:
        node = Node(insertVal)
        node.next = node
        return node

    values = [insertVal]
    cur = head
    while True:
        values.append(cur.val)
        cur = cur.next
        if cur is head:
            break

    values.sort()
    nodes = [Node(value) for value in values]
    for i in range(len(nodes)):
        nodes[i].next = nodes[(i + 1) % len(nodes)]
    return nodes[0]

⚡ Approach 2: One Pass Around the Circle (Best)

The idea in one line: walk the circle once and splice the new node at the first spot that fits.

The idea:

Start at the given node. Move with two pointers, cur and cur.next.
At each step, test if the new value belongs between them.

How it works:

Stop if the value sits between cur and cur.next in normal order.
Stop at the seam where cur.val > cur.next.val if the value is a new max or a new min.
Stop if you loop back to the start with no fit, which means all values are equal.
Then splice: point the new node’s next to cur.next, then point cur.next to the new node.

Why it is fast:

It walks the circle at most once. So it is O(n).
It adds only a single node. So the extra space is O(1).
The list stays sorted with no rebuild.

Steps to Solve

If the given pointer is null, make a node that points to itself and return it.
Set cur to the start node. Walk with cur and cur.next.
If cur.val <= insert <= cur.next.val, insert between them and stop.
If cur.val > cur.next.val and the value is a new max or new min, insert at the seam and stop.
Move cur forward. If you return to the start, insert after cur because all values are equal.
Splice the new node in and return the original start node.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version walks the circle once with cur and cur.next, handling the empty list, the seam, and the all-equal case.

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


def insert(start, value):
    node = Node(value)
    if start is None:                 # empty list
        node.next = node
        return node

    cur = start
    while True:
        if cur.val <= value <= cur.next.val:
            break                     # fits between cur and next
        if cur.val > cur.next.val:    # the wrap seam
            if value >= cur.val or value <= cur.next.val:
                break                 # new max or new min
        cur = cur.next
        if cur == start:              # looped once, all equal
            break

    node.next = cur.next              # splice the new node in
    cur.next = node
    return start


def build_circular(values):
    head = Node(values[0])
    cur = head
    for v in values[1:]:
        cur.next = Node(v)
        cur = cur.next
    cur.next = head                   # close the circle
    return head


def read_sorted(start):
    min_node = start
    cur = start.next
    while cur != start:               # find the smallest node
        if cur.val < min_node.val:
            min_node = cur
        cur = cur.next
    out = []
    cur = min_node
    while True:
        out.append(str(cur.val))
        cur = cur.next
        if cur == min_node:
            break
    return " -> ".join(out)


start = build_circular([3, 4, 1])
start = insert(start, 2)
print(read_sorted(start))

The output of the above code will be:

1 -> 2 -> 3 -> 4

Let us read the Python insert function line by line, because the stopping conditions are the whole trick.

We make the new node first. If start is None, the list is empty. So the new node points to itself and becomes a one-node circle. We return it.

Otherwise we set cur to start and loop. The first test is the normal case. If cur.val <= value <= cur.next.val, the value fits neatly between two neighbors. So we break and insert there.

The second test handles the seam. The seam is the single spot where the largest value points back to the smallest, so cur.val > cur.next.val. If we are at the seam and the value is at least the largest, or at most the smallest, it belongs right here. A new maximum goes after the biggest. A new minimum also goes here, because the next node is the smallest. So both extremes splice at the same seam.

The third test guards against an endless loop. We move cur forward. If cur comes back to start, we have gone around once with no fit. That happens when every value is equal. So we just break and insert wherever we stopped.

After the loop, the splice is the same two lines every time. We point node.next to cur.next, then point cur.next to node. We return the original start, since the problem lets us return any node.

⏱️ Time and Space Complexity

We walk the circle at most one full time, so the work is O(n), where n is the number of nodes. The splice itself is O(1). We add a single node, so the extra space is O(1). There is no faster way, because in the worst case the right spot is at the far end of the loop.

Approach	Time Complexity	Space Complexity
Gather, sort, rebuild (brute force)	O(n log n)	O(n)
One pass around the circle	O(n)	O(1)

Tip

The endless-loop guard matters. When every value in the list is equal, no comparison ever passes. Without the check for returning to the start, your loop would spin forever. Always add that stop.

🧩 Key Takeaways

✅ A sorted circular list wraps from the largest value back to the smallest at one seam.
✅ The normal insert is when the value fits between two neighbors in increasing order.
✅ A new maximum or a new minimum both belong at the seam, where the order flips.
✅ If every value is equal, no test passes, so insert anywhere after one full loop.
✅ Always stop when you return to the start, or an all-equal list loops forever.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Reverse a Linked List
Merge Two Sorted Lists

Previous LFU Cache Next Valid Parentheses

Insert into a Sorted Circular Linked List

Follow Us

Follow Us