• Leetcode 708 (Premium)
• Difficulty: Medium

---

Problem Definition

Given a node from a circular linked list which is sorted in non-decreasing order, write a function to insert a value into the list such that the order is preserved. The given node can be anywhere in the linked list. The new item can be inserted anywhere if there are multiple suitable locations. If the list is empty, then create a new cyclic list and return it. Return a reference to the new item inside the circular linked list.

---

Item Class

The class representing an item in the linked list.

class Item:
    def __init__(self, val: int, nxt: 'Item' = None):
        self.val = val
        self.nxt = nxt

    def __len__(self):
        s = 1
        curr = self.nxt
        while curr != self:
            s += 1
            curr = curr.nxt
        return s

---

Examples

Some test cases to verify our solution.

# 0->1->2->3->5->0
five = Item(5)
three = Item(3, nxt=five)
two = Item(2, nxt=three)
one = Item(1, nxt=two)
zero = Item(0, nxt=one)
five.nxt = zero
four = insert_val(two, 4)
assert four.nxt == five, (four.nxt.val, three.nxt.val, five.nxt.val)
assert three.nxt == four
for i in (zero, one, two, three, four, five):
    assert len(i) == 6

seven = insert_val(zero, 7)
nine = insert_val(three, 9)
six = insert_val(nine, 6)
six_2 = insert_val(five, 6)
assert six_2.nxt == seven or six.nxt == seven, (six, six_2)
assert five.nxt == six_2 or five.nxt == six
assert seven.nxt == nine, seven
assert nine.nxt == zero, nine
for i in (zero, one, two, three, four, five, six, six_2, seven, nine):
    assert len(i) == 10

new_one = insert_val(None, 1)
assert len(new_one) == 1
assert new_one.nxt == new_one

---

Solution

def insert_val(start: Item, num: int) -> Item:
    item = Item(num)
    if head is None:
        item.nxt = item
        return item
    prev = head
    curr = head.nxt
    while curr != head:
        if prev.val <= num and num < curr.val or (prev.val > curr.val and (num > prev.val or num < curr.val)):
            break
        prev = curr
        curr = curr.nxt
    prev.nxt = item
    item.nxt = curr
    return item

---

Complexity

Let $n = $ the number of nodes in the circular linked list.

Since we are traversing the circular linked list once, runtime complexity should be $\Theta(n)$.

Auxiliary space complexity should be $\Theta(1)$.