Insert into a Sorted Circular Linked List — Edge Case Mastery Explained

Problem Statement#

LeetCode 708 — Insert into a Sorted Circular Linked List Difficulty: Medium | Pattern: Circular List Traversal + Case Analysis

Given a node from a sorted circular linked list, insert a value into the list such that it remains a sorted circular list. Return the inserted node. If the list is empty (the given node is null), create a new single-node circular list and return that node.

Constraints:

• 0 <= Number of nodes <= 5 * 10^4
• -10^6 <= Node.val, insertVal <= 10^6
• The given node can be any node in the list.

Example 1:

Input:  head = [3, 4, 1], insertVal = 2
Output: [3, 4, 1, 2]
Explanation: After insertion (sorted circular): ... -> 1 -> 2 -> 3 -> 4 -> ...

Example 2:

Input:  head = [], insertVal = 1
Output: [1]  (circular: 1 -> 1)

Example 3:

Input:  head = [1], insertVal = 0
Output: [1, 0]  (circular: 0 -> 1 -> 0 or 1 -> 0 -> 1)

Why This Problem Matters#

This problem is a premium LeetCode problem (previously Facebook/Google locked) that tests your ability to think systematically about circular data structures. Google and Facebook use it in interviews because getting it right requires handling exactly three distinct cases — and most candidates either miss one case entirely or handle the wrong condition for the wrap-around case.

Circular linked lists appear in real systems: OS process scheduling (round-robin scheduler uses a circular list of processes), game turn management, and audio/video ring buffers. The insertion problem captures exactly the kind of edge case reasoning that distinguishes a solid systems programmer.

What makes this problem genuinely hard is that the entry point could be any node — not necessarily the minimum. You must traverse the circular list correctly, recognize the seam (where the maximum wraps around to the minimum), and correctly identify all positions where the new value fits.

Interviewers use this problem to watch how candidates enumerate cases methodically: "what if the value is in the normal range?", "what if it is greater than the maximum?", "what if it is less than the minimum?", "what if all values are equal?" Each case requires different condition logic.

The Core Insight#

The three cases for insertion in a sorted circular list:

Case 1 — Normal range: curr.val <= insertVal <= curr.next.val The new value fits between curr and curr.next in sorted order. Insert here.

Case 2 — Wrap-around position: curr.val > curr.next.val This is the seam where maximum wraps around to minimum. Insert here if:

• insertVal >= curr.val (new value is a new maximum), or
• insertVal <= curr.next.val (new value is a new minimum)

Case 3 — Full traversal (all values equal): curr.next == head We have gone all the way around without finding a position. Insert anywhere — between curr and curr.next is fine.

The algorithm traverses the list checking these cases in order, stopping at the first match.

Visual Dry Run#

Input: [3, 4, 1] (sorted circular: 1 -> 3 -> 4 -> 1 ...), insertVal = 2

Starting at head (any node — say node(3)):

Insert node(2) between node(1) and node(3): node(2).next = node(3), node(1).next = node(2)

Circular list: ... -> 1 -> 2 -> 3 -> 4 -> 1 -> ...

All-equal case: [3, 3, 3], insertVal = 0

Walk all the way around: none of Case 1 or Case 2 match. At curr.next == head, break and insert — result: [3, 3, 3, 0] (order within equals is irrelevant for sorted circular property).

Solution (Optimal)#

class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
 
def insert(head: 'Node', insertVal: int) -> 'Node':
    new_node = Node(insertVal)
 
    # Case: empty list
    if not head:
        new_node.next = new_node
        return new_node
 
    curr = head
    while True:
        # Case 1: insertVal fits in normal sorted order
        if curr.val <= insertVal <= curr.next.val:
            break
 
        # Case 2: curr is the maximum (wrap-around seam)
        if curr.val > curr.next.val:
            if insertVal >= curr.val or insertVal <= curr.next.val:
                break
 
        # Case 3: full traversal without finding position
        if curr.next == head:
            break
 
        curr = curr.next
 
    # Insert new_node after curr
    new_node.next = curr.next
    curr.next = new_node
    return head

function insert(head, insertVal) {
    const newNode = { val: insertVal, next: null };
 
    // Case: empty list
    if (!head) {
        newNode.next = newNode;
        return newNode;
    }
 
    let curr = head;
    while (true) {
        // Case 1: normal sorted position
        if (curr.val <= insertVal && insertVal <= curr.next.val) {
            break;
        }
 
        // Case 2: at the seam (max -> min wrap-around)
        if (curr.val > curr.next.val) {
            if (insertVal >= curr.val || insertVal <= curr.next.val) {
                break;
            }
        }
 
        // Case 3: full traversal — insert anywhere
        if (curr.next === head) {
            break;
        }
 
        curr = curr.next;
    }
 
    newNode.next = curr.next;
    curr.next = newNode;
    return head;
}

Complexity:

Common Mistakes#

1. Missing the all-equal case: If all values are equal, neither Case 1 nor Case 2 ever triggers. Without the curr.next == head check, the loop runs forever.
2. Wrong seam condition: Case 2 triggers when curr.val > curr.next.val. The insertion condition is insertVal >= curr.val OR insertVal <= curr.next.val — both must be checked with OR, not AND.
3. Returning head when head should change: The problem says to return the same head node that was given. Even if you insert before the given head, the circular structure ensures returning head is always correct.
4. Not handling the empty list: When head is null, create a single-node circular list where new_node.next = new_node.
5. Checking curr.next == head inside the seam block: The full-traversal check must be outside the seam block — it is a fallback for all cases, not just the seam case.

Interview Tips#

• Enumerate cases before coding: "I see three cases: normal range, wrap-around seam, and all-equal fallback. Let me handle each."
• Draw the circular list: Sketching the ring with arrows makes the seam (max-to-min transition) visually obvious and prevents confusion.
• Explain the seam condition: "When curr.val > curr.next.val, we are at the maximum. The new value either becomes the new max (>= curr.val) or the new min (<= curr.next.val)."
• Test the all-equal case explicitly: "If all nodes are 5 and insertVal is 3, no case triggers until we complete the loop — then Case 3 catches it."
• Confirm what the return value should be: The problem asks to return the inserted node, but the solution above returns head. Check the problem statement carefully — LeetCode 708 asks for the inserted node in some variants.

Follow-up Questions#

1. What if you must return the inserted node instead of the head? Change the return to new_node instead of head.
2. What if the list is not sorted? You cannot use sorted position logic. You would need a different insertion rule (e.g., insert after the current node).
3. Implement a full circular linked list class: Add insert, delete, and search methods. Discuss how the lack of a null terminator complicates all operations.
4. OS process scheduling uses a circular list: Describe how a round-robin scheduler uses a circular linked list of processes and how inserts/deletes maintain the schedule.
5. What if the list could have duplicate values at the seam? The current Case 2 condition handles duplicates correctly — the OR logic covers all boundary cases.

Key Takeaways#

• A sorted circular list has a seam: the point where the maximum wraps around to the minimum. curr.val > curr.next.val identifies this seam.
• Three cases cover all insertions: normal range, seam (new max or new min), and all-equal fallback after a full traversal.
• The all-equal fallback uses curr.next == head to detect a complete traversal and insert anywhere.
• Always handle the empty list case: create a new single-node circular list with new_node.next = new_node.
• The insertion point is always after curr — set new_node.next = curr.next; curr.next = new_node.
• This problem rewards systematic case enumeration — sketch cases on paper first, then translate each to code.