Insert Into a Sorted Circular List

Interview Problem Interview Medium Same-direction Pointers Array Linked List

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.insert(values, insertVal). values serializes one full traversal of a nondecreasing circular list starting at its minimum; return the same anchored traversal after insertion. Return [insertVal] for empty input.

Starter code

class Solution:
    def insert(self, values, insertVal):
        pass

Test cases

middle

{
  "args": [
    [
      1,
      3,
      4
    ],
    2
  ]
}

Expected: [1,2,3,4]

Wizard outline

Step 1: Initialize Solution.insert
Replace the empty starter with the first real state owned by Solution.insert. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Empty case
Complete the readable core algorithm for one representative Interview case. Insert between adjacent values when they bracket the target, including the circular wrap boundary.
Step 3: Harden the Middle boundary
Repair the reviewed boundary and pass the complete submission contract. The anchored traversal is nondecreasing. Inserting at its lower-bound position preserves nondecreasing order and represents the same circular sorted invariant; a new minimum correctly becomes the new anchor.

Footguns and prerequisites

When all values are equal, any gap is valid; the anchored serialized result still needs deterministic ordering.
linked lists
arrays strings two pointers sliding window

Reviewed references

LeetCode 708 — Insert into a Sorted Circular Linked List

Practice prerequisites

Relink Nodes Safely(opens in a new tab)
Relink Nodes Safely isolates every untouched node keeps its original next link, and at most one predecessor changes to the removed node’s former successor. That focused state discipline is required when implementing insert sorted circular values as a complete Interview Problem.

Recommended approach and implementation

Because serialization is anchored at the minimum, lower-bound the first value not less than insertVal, insert there, and keep the minimum at index zero.

Why it works: The anchored traversal is nondecreasing. Inserting at its lower-bound position preserves nondecreasing order and represents the same circular sorted invariant; a new minimum correctly becomes the new anchor.

class Solution:
    def insert(self, values, insertVal):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        output = values[:]
        index = 0
        while index < len(output) and output[index] < insertVal:
            index += 1
        output.insert(index, insertVal)
        return output