AlgoMaster Logo

Insert into a Sorted Circular Linked List

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have a circular linked list where the nodes are sorted in ascending order, but the "start" of the list can be any node. Because it's circular, the last (largest) node points back to the first (smallest) node, creating a wrap-around point. We need to insert a new value while keeping the sorted order intact.

The complication is that the given head pointer might not be the smallest node, so we cannot assume we are starting from the beginning of the sorted sequence. We have to find the insertion point by examining the relationship between each pair of consecutive nodes.

There are three distinct cases to think about:

  1. Normal insertion: The new value fits between two consecutive nodes (e.g., inserting 3 between 2 and 5).
  2. Boundary insertion: The new value is either larger than the maximum or smaller than the minimum, so it belongs at the wrap-around point where the list goes from the largest value back to the smallest.
  3. Uniform list: All nodes have the same value, so any position works.

Key Constraints:

  • 0 <= number of nodes <= 5 * 10^4 → The list can be empty, which is a special case we must handle. With up to 50,000 nodes, we need an O(n) or better approach.
  • -10^6 <= Node.val, insertVal <= 10^6 → Values can be negative. Don't assume positive-only values.

Approach 1: Two-Pass (Find Boundary, Then Insert)

Intuition

First understand the structure of the list, then decide where to insert.

In the first pass, we walk around the circular list to find the boundary where the largest node connects back to the smallest node. This is the single point where prev.val > curr.val. Once we know the boundary, we know both the maximum value (the node before the boundary) and the minimum value (the node after it), which fixes the sorted order of the whole list.

The second pass decides where insertVal belongs:

  • If insertVal is greater than or equal to the max or less than or equal to the min, it is a new extreme value and belongs at the boundary.
  • Otherwise, it falls somewhere inside the sorted range, so we start from the minimum node and walk forward until two consecutive nodes satisfy prev.val <= insertVal <= curr.val.

This separates the two concerns cleanly at the cost of traversing the list twice.

Algorithm

  1. Handle the empty list edge case: if head is null, create a new node that points to itself and return it.
  2. First pass: traverse the circular list to find the boundary (where prev.val > curr.val). Track the node with the maximum value.
  3. Determine insertion position:
    • If insertVal >= max value or insertVal <= min value, insert at the boundary.
    • Otherwise, start from the min node and walk forward until prev.val <= insertVal <= curr.val.
  4. Insert the new node between prev and curr.
  5. Return the original head.

Visualization and Code

Loading animation...

This approach traverses the list twice. The next approach checks all three insertion conditions at every node, which finds the insertion point in a single pass.

Approach 2: One-Pass with Inline Case Handling (Optimal)

Intuition

Instead of first finding the boundary and then finding the insertion point, we can do everything in one traversal. We walk the list with two pointers (prev and curr) and check at each step whether this is the right place to insert.

There are three conditions, and we insert as soon as any of them is satisfied:

  1. Normal range: prev.val <= insertVal <= curr.val. The new value fits between these two consecutive nodes.
  2. Boundary (wrap-around): We're at the point where the list wraps from the largest to the smallest value (prev.val > curr.val), and insertVal is either greater than or equal to prev.val (larger than the max) or less than or equal to curr.val (smaller than the min).
  3. Full loop: We've gone all the way around and are back to the starting node. This happens when all values are the same. Just insert anywhere.

Algorithm

  1. Handle the empty list edge case: if head is null, create a new node pointing to itself and return it.
  2. Initialize prev = head and curr = head.next.
  3. Loop through the circular list:
    • Check if prev.val <= insertVal <= curr.val (normal insertion).
    • Check if prev.val > curr.val (we're at the boundary) AND (insertVal >= prev.val OR insertVal <= curr.val).
    • If either condition is true, insert between prev and curr and return.
    • Otherwise, advance both pointers.
  4. If we complete a full loop without inserting (all values are equal), insert between prev and curr (any position works).
  5. Return the original head.

Visualization and Code

Loading animation...