← DSA Atlas
Dedicated problem page · #708

Insert into a Sorted Circular Linked List

MediumLinked Lists and Pointer ManipulationLocate insertion gap in a circular sorted listSingle traversal with wrap-around case analysis
Solve on LeetCode ↗
708
MediumLinked Lists and Pointer ManipulationSingle traversal with wrap-around case analysisLocate insertion gap in a circular sorted list

Insert into a Sorted Circular Linked List

Given a reference to any node in a non-decreasing sorted circular singly linked list, insert a new node with value insertVal so the list stays sorted, and return a reference to the (possibly new) head. If the given reference is null, create a single self-pointing node and return it.

Open official problem prompt ↗
In plain English

Splice a new value into a circular sorted linked list so the non-decreasing order is preserved, no matter which node you were handed.

Picture it like this

Adding a new hour label to a clock face that runs 1..12 and wraps back to 1; you place it in the correct arc, and if it is larger than 12 or smaller than 1 it goes at the 12-to-1 seam.

Example
Input
head = [3,4,1] (a circular list 3 -> 4 -> 1 -> back to 3), insertVal = 2
Output
[3,4,1,2]
Why
In sorted order the values are 1,3,4; inserting 2 between 1 and 3 keeps it sorted, giving the cycle 3 -> 4 -> 1 -> 2 -> back to 3.
Constraints
The number of nodes is in the range [0, 5 * 10^4]-10^6 <= Node.val <= 10^6-10^6 <= insertVal <= 10^6The list is sorted in non-decreasing order and is circular
Pattern lesson

See the pattern, then code

Locate insertion gap in a circular sorted list
Recognition clue

You are given one node of a circular sorted list and must keep sortedness after inserting. The circularity plus the fact that the given node may be anywhere in the cycle signals a one-lap scan checking for the correct gap, including the wrap-around point.

↗
Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. Walk the cycle once with a prev/cur pair. Insert where prev.val <= insertVal <= cur.val. The only tricky spot is the seam where the maximum wraps to the minimum (prev.val > cur.val): a value larger than the max or smaller than the min belongs exactly there. If no spot is found after a full lap (all values equal), insert anywhere.

New words, made simpleKnow these before the algorithm
Circular linked list
A list whose last node points back to the first, so there is no null tail.
Wrap-around seam
The single edge where the largest value links to the smallest value.
Non-decreasing order
Each value is greater than or equal to the previous one, allowing duplicates.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Collect, sort, rebuild

Works but wastes time and memory and destroys the existing nodes unnecessarily.

Traverse the cycle into an array, add the value, sort, and rebuild a circular list.

Time O(n log n)Space O(n)
Best choiceOne-lap prev/cur scan

Optimal single pass that handles every ordering case with simple comparisons.

Walk once, inserting at the first fitting gap or at the max-to-min seam, and insert anywhere if all values are equal.

Time O(n)Space O(1)
The rule we keep true

Invariant

prev and cur are always adjacent in the cycle, and the algorithm inserts only when insertVal fits the arc between prev and cur under normal or wrap-around ordering.

Why this is correct

Reasoning

In a sorted circular list there is at most one descending edge (the seam). For a normal ascending edge, prev.val <= insertVal <= cur.val identifies the correct gap. At the seam, values beyond the current max or below the current min both belong there. If neither condition ever triggers, every value is equal, so any gap is valid and we stop after one full lap to avoid an infinite loop.

The algorithm in three movesSay these aloud before coding
1If head is null, make a node pointing to itself and return it

prev=1, cur=3 (head)

2Walk prev and cur around the cycle

1 <= 2 <= 3 -> insert here

3Insert if prev.val <= insertVal <= cur.val

1 -> 2 -> 3 ... cycle intact

4At the max-to-min seam, insert if insertVal is >= the max or <= the min

5If a full lap completes with no fit, insert before returning to head

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
41
12
(2)3
1 · Readhead=3, insertVal=2
2 · AskDoes 2 fit between 3 and 4?
3 · Update stateprev=3, cur=4
4 · Result3<=2 is false; not the seam; advance
Key takeaway

The new value 2 slots into the gap between 1 and 3 in the circular order.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Empty-list case

    With no head, create a lone node whose next points to itself, forming a valid one-element cycle.

  2. 2
    Lines 7-8Set up adjacent pointers

    prev starts at head and cur one ahead so we can inspect each edge of the cycle.

  3. 3
    Lines 9-18Scan for the gap

    Break on a normal fitting edge, or on the max-to-min seam when the value is an new extreme; break after a full lap (cur is head) to guarantee termination when all values are equal.

  4. 4
    Lines 19-21Splice and return

    Link prev to the new node and the new node to cur; the original head reference is still valid, so return it.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty list (head is null) -> return a self-pointing node
  • Single-node list
  • insertVal larger than every value (goes at the seam after the max)
  • insertVal smaller than every value (goes at the seam before the min)
  • All node values equal (insert after one full lap)
  • Duplicate value equal to some existing node
!

Common beginner mistakes

  • Looping without the `cur is head` termination check causes an infinite loop when all values are equal
  • Handling only prev.val <= insertVal <= cur.val forgets the wrap-around seam and mishandles new extremes
  • Returning the new node instead of the original head reference (the problem expects the head reference back)
  • Using strict < comparisons breaks placement of duplicate values
Check your understanding

Why is the `if cur is head: break` line essential rather than optional?

More in Linked Lists and Pointer Manipulation

#206Reverse Linked ListIterative pointer reversal#141Linked List CycleFast and slow pointers (Floyd's cycle detection)#143Reorder ListFind middle, reverse second half, merge alternately#138Copy List with Random PointerClone with old-to-new node mapping#146LRU CacheHash map plus recency-ordered structure#2Add Two NumbersDigit-by-digit addition with carry