Problem Description

You are given a circular linked list that is sorted in non-descending order (ascending order with possible duplicates). Your task is to insert a new value insertVal into this list while maintaining the sorted order.

Key points about the problem:

1. Circular Linked List: The last node points back to the first node, forming a circle with no null references in the next pointers.

2. Sorted in Non-Descending Order: The values are arranged such that each node's value is less than or equal to the next node's value (e.g., 1 → 2 → 3 → 3 → 4 → 1... where the last 1 connects back to the first).

3. Given Node: You receive a reference to any single node in the list, not necessarily the smallest or first node.

4. Insertion Rules:

   • Insert insertVal at any suitable position that maintains the sorted order
   • If multiple valid positions exist, you can choose any one
   • The list should remain circular and sorted after insertion

5. Edge Cases:

   • If the list is empty (head is null), create a new single-node circular list containing insertVal and return it
   • Otherwise, return the original head node that was given

The solution needs to handle three main scenarios for insertion:

• Normal case: Insert between two nodes where prev.val ≤ insertVal ≤ curr.val
• Boundary case: Insert at the transition point where the largest value connects back to the smallest value (when prev.val > curr.val)
• Empty list case: Create a new circular list with just one node

The algorithm traverses the circular list to find the appropriate insertion point, creates a new node with insertVal, and adjusts the pointers to maintain the circular structure while preserving the sorted order.

Intuition

To understand how to insert into a sorted circular linked list, let's think about what makes this problem unique. In a regular sorted linked list, we'd simply find where the value fits and insert it. But in a circular list, there's no clear "beginning" or "end" - it's a continuous loop.

The key insight is recognizing that even though the list is circular, there are only a few distinct positions where we can insert a value:

1. Between two nodes in the sorted sequence: This is the most straightforward case. If we have nodes with values like 3 → 5 → 7, and we want to insert 6, it clearly goes between 5 and 7.

2. At the "wrap-around" point: In a circular sorted list, there's exactly one place where a larger value points to a smaller value - where the maximum connects back to the minimum. For example, in 1 → 3 → 5 → 1..., the transition from 5 to 1 is special. This is where we'd insert values that are either larger than the maximum or smaller than the minimum.

The challenge is that we might start traversing from any node, not necessarily the smallest one. So we need to keep moving through the list looking for one of these insertion points.

Our strategy becomes:

• Use two pointers (prev and curr) to examine consecutive pairs of nodes
• Check if insertVal fits between them: prev.val ≤ insertVal ≤ curr.val
• If not, check if we're at the wrap-around point (prev.val > curr.val), and if so, whether insertVal should go there (either it's bigger than the max or smaller than the min)
• Keep moving forward until we find the right spot or complete a full circle

The beauty of this approach is that we're guaranteed to find a valid insertion point within one complete traversal of the list. If we've gone all the way around without finding a spot, it means all values in the list are the same, and we can insert anywhere - so we just insert after the head.

For an empty list, we simply create a self-referencing node (pointing to itself) to maintain the circular property.

Learn more about Linked List patterns.

Solution Approach

Let's walk through the implementation step by step:

1. Handle the Empty List Case

if head is None:
    node.next = node
    return node

When the list is empty, we create a new node that points to itself, forming a single-node circular list.

2. Set Up Two Pointers for Traversal

prev, curr = head, head.next

We initialize two pointers: prev starts at the given head node, and curr starts at the next node. These will help us examine consecutive pairs of nodes to find the insertion point.

3. Traverse the Circular List

while curr != head:

We continue traversing until curr comes back to head, meaning we've completed one full circle through the list.

4. Check for Valid Insertion Points

Inside the loop, we check two conditions:

if prev.val <= insertVal <= curr.val or (
    prev.val > curr.val and (insertVal >= prev.val or insertVal <= curr.val)
):
    break

First condition: prev.val <= insertVal <= curr.val

• This handles the normal case where insertVal fits between two consecutive nodes in the sorted sequence
• For example, if we have 3 → 5 and want to insert 4, this condition is satisfied

Second condition: prev.val > curr.val and (insertVal >= prev.val or insertVal <= curr.val)

• The first part prev.val > curr.val identifies the wrap-around point (where max connects to min)
• At this special point, we insert if:
  • insertVal >= prev.val: The value is greater than or equal to the maximum (goes after the max)
  • insertVal <= curr.val: The value is less than or equal to the minimum (goes before the min)
• For example, in a list 2 → 4 → 1 → 2..., the transition 4 → 1 is the wrap-around point. We'd insert 5 or 0 here.

5. Move Pointers Forward

prev, curr = curr, curr.next

If we haven't found the insertion point yet, we advance both pointers to check the next pair of nodes.

6. Perform the Insertion

prev.next = node
node.next = curr
return head

Once we find the correct position (or complete a full traversal), we insert the new node between prev and curr by:

• Making prev point to the new node
• Making the new node point to curr
• Returning the original head reference

Edge Case Handling: If all nodes have the same value (e.g., 3 → 3 → 3 → 3...), the loop completes without breaking, and we insert after head by default, which maintains the sorted property since all values are equal.

The time complexity is O(n) where n is the number of nodes, as we traverse at most once through the entire list. The space complexity is O(1) as we only use a constant amount of extra space for the new node and pointers.

Example Walkthrough

Let's walk through inserting value 4 into a circular sorted linked list: 1 → 3 → 5 → 1... (where 5 points back to 1).

Suppose we're given a reference to the node with value 3 as our head.

Initial Setup:

• Create new node with value 4
• Set prev = 3 (head) and curr = 5 (head.next)

First Iteration:

• Check: Is 3 ≤ 4 ≤ 5? Yes! ✓
• This is our insertion point - break from loop

Insertion:

• Set prev.next = node(4) → Now 3 points to 4
• Set node.next = curr → Now 4 points to 5
• Final list: 1 → 3 → 4 → 5 → 1...
• Return the original head (node 3)

Another Example - Wrap-around Case:

Insert value 6 into the same list: 1 → 3 → 5 → 1..., starting from node 3.

Iteration 1:

• prev = 3, curr = 5
• Check: Is 3 ≤ 6 ≤ 5? No
• Move forward: prev = 5, curr = 1

Iteration 2:

• prev = 5, curr = 1
• Check: Is 5 ≤ 6 ≤ 1? No
• But wait! Is 5 > 1? Yes - this is the wrap-around point
• Is 6 ≥ 5? Yes! ✓
• This is our insertion point - break

Insertion:

• Insert 6 between 5 and 1
• Final list: 1 → 3 → 5 → 6 → 1...

The algorithm correctly identifies that 6 should go after the maximum value 5, right at the wrap-around point where the list cycles back to the minimum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the circular linked list.

The algorithm traverses the circular linked list at most once. In the worst case, when the insertion point is right before the head node, the while loop will iterate through all n nodes in the list before finding the correct position to insert. Each iteration performs constant time operations (comparisons and pointer assignments), so the overall time complexity is linear.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. It creates one new node for insertion and uses two pointer variables (prev and curr) to traverse the list. These space requirements do not depend on the size of the input list, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Single-Node List Case Properly

Pitfall: When the circular list contains only one node (where head.next == head), the standard traversal logic with curr = head.next will immediately satisfy the condition curr == head, causing the while loop to never execute. This means the insertion logic inside the loop is never checked, and the new node is always inserted after head, which may not be correct.

Example: If we have a single node with value 3 and want to insert 1, the value 1 should logically come before 3 in a sorted list, but the code would insert it after 3.

Solution: Add a special check for single-node lists:

# After handling empty list
if head.next == head:
    # Single node case - always insert after head
    head.next = new_node
    new_node.next = head
    return head

However, in a circular sorted list, any position maintains the sorted property since it's circular, so this is more of a logical consideration than a bug.

2. Incorrectly Identifying the Wrap-Around Point

Pitfall: The condition prev_node.val > curr_node.val alone isn't sufficient to handle all edge cases at the boundary. Consider a list where all values are the same (e.g., 3 → 3 → 3). In this case, prev_node.val > curr_node.val will never be true, and if insertVal is different from these values (say 5 or 1), it might not find the correct insertion point.

Solution: Ensure the traversal completes a full circle even when no explicit boundary is found:

# Add a flag to track if we've found an insertion point
insert_position_found = False

while curr_node != head:
    if prev_node.val <= insertVal <= curr_node.val:
        insert_position_found = True
        break
  
    if prev_node.val > curr_node.val:
        if insertVal >= prev_node.val or insertVal <= curr_node.val:
            insert_position_found = True
            break
  
    prev_node = curr_node
    curr_node = curr_node.next

# If no position found (all same values), insert anywhere is valid
prev_node.next = new_node
new_node.next = curr_node

3. Boundary Value Comparison Errors

Pitfall: Using strict inequalities (< and >) instead of <= and >= can cause issues with duplicate values. For example, if we have 2 → 3 → 4 and want to insert 3, using prev_node.val < insertVal < curr_node.val would miss the valid insertion position between the first 2 and 3.

Solution: Always use inclusive comparisons (<= and >=) to handle duplicates correctly:

# Correct: handles duplicates
if prev_node.val <= insertVal <= curr_node.val:
    break

# Incorrect: might miss valid positions with duplicates
if prev_node.val < insertVal < curr_node.val:
    break

4. Infinite Loop Risk

Pitfall: If the circular list structure is corrupted (not properly circular) or if there's a bug in pointer advancement, the traversal could run indefinitely.

Solution: Add a safety mechanism to detect if we've traversed more nodes than expected:

max_iterations = 0
curr_node = head.next

# Count nodes first (optional safety check)
temp = head.next
while temp != head and max_iterations < 10000:  # arbitrary large limit
    max_iterations += 1
    temp = temp.next

if max_iterations >= 10000:
    # Handle corrupted list
    return head

# Now traverse with confidence
iterations = 0
while curr_node != head and iterations < max_iterations:
    # ... insertion logic ...
    iterations += 1
    prev_node = curr_node
    curr_node = curr_node.next

These pitfalls highlight the importance of thorough testing with edge cases including empty lists, single-node lists, lists with all identical values, and values at the extremes of the existing range.