LC 708: Insert into a Sorted Circular Linked List

Difficulty: Medium
Category: Linked List, Circular List
Companies: Amazon, Facebook, Google, Microsoft

Problem Statement

Given a circular linked list, represented by a Node class, insert a new value into the list while maintaining the circular and sorted order of the list.

The list is circular, so the last node points back to the first node. The list is sorted in ascending order.

Examples

Example 1:

Input: head = [3,4,1], insertVal = 2
Output: [3,4,1,2]
Explanation: Insert 2 between 1 and 3, maintaining the circular sorted order.

Example 2:

Input: head = [], insertVal = 1
Output: [1]
Explanation: Create a circular list with a single node.

Example 3:

Input: head = [1], insertVal = 0
Output: [1,0]
Explanation: Insert 0 between 1 (tail) and 1 (head), wrapping around.

Constraints

  • The number of nodes in the list is in the range [0, 5 * 10^4]
  • -10^6 <= Node.val, insertVal <= 10^6
  • List is sorted in ascending order
  • List is circular

Solution Approaches

Key Insight: Traverse the circular list once and look for a valid insertion point. Handle edge cases at the wrap-around point.

Algorithm:

  1. Handle empty list by creating a self-referencing node
  2. Traverse the circular list
  3. Find insertion point where curr->val <= insertVal && curr->next->val >= insertVal
  4. Handle wrap-around case where curr->next->val < curr->val (wrap point)
    • Insert if insertVal >= curr->val OR insertVal <= curr->next->val
  5. If no valid point found after full traversal, insert after current position

Time Complexity: O(n) where n is the number of nodes
Space Complexity: O(1)

/
# Definition for a Node.
class Node:
def __init__(self, _val: int = 0, _next: 'Node | None' = None):
self.val = _val
self.next = _next
/
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
# Empty list case
if not head:
newNode = Node(insertVal)
newNode.next = newNode
return newNode
curr = head
toInsert = False
while True:
# Normal case: insert between curr and curr.next
if curr.val <= insertVal <= curr.next.val:
toInsert = True
# Wrap-around case: curr.next.val < curr.val indicates the wrap point
elif curr.next.val < curr.val:
# Insert at wrap-around (largest or smallest value)
if insertVal >= curr.val or insertVal <= curr.next.val:
toInsert = True
if toInsert:
newNode = Node(insertVal)
newNode.next = curr.next
curr.next = newNode
return head
curr = curr.next
if curr == head:
break
# All values are the same or insert at current position
newNode = Node(insertVal, curr.next)
curr.next = newNode
return head

Approach 2: Two-Pass with Preprocessing

Algorithm:

  1. First pass: Find the node with maximum value
  2. Second pass: Search from max node’s next to find insertion point
  3. Handle all same values case

Time Complexity: O(n)
Space Complexity: O(1)

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if not head:
            newNode = Node(insertVal)
            newNode.next = newNode
            return newNode
            # Find the maximum node
            maxNode = head
            curr = head.next
            while curr != head:
                if curr.val >= maxNode.val:
                    maxNode = curr
                    curr = curr.next
                    # Insert at the end if value is too large
                    if insertVal >= maxNode.val or insertVal <= maxNode.next.val:
                        newNode = Node(insertVal, maxNode.next)
                        maxNode.next = newNode
                        return head
                        # Find the correct insertion point
                        curr = maxNode.next
                        while curr.next.val < insertVal:
                            curr = curr.next
                            newNode = Node(insertVal, curr.next)
                            curr.next = newNode
                            return head

Approach 3: Simplified Logic

Algorithm: Streamlined version that handles all cases more elegantly.

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        newNode = Node(insertVal)
        if not head:
            newNode.next = newNode
            return newNode
            curr = head
            while curr.next != head:
                if curr.val <= insertVal <= curr.next.val:
                    break
                    if curr.val > curr.next.val and (insertVal >= curr.val or insertVal <= curr.next.val):
                        break
                        curr = curr.next
                        newNode.next = curr.next
                        curr.next = newNode
                        return head

Algorithm Analysis

Key Insights

  1. Circular List Boundary: The “wrap” happens when curr->val > curr->next->val
  2. Insertion Point Detection: Need to check both normal range and wrap-around cases
  3. Edge Cases: Empty list, single node, all same values
  4. Traversal Guard: Use do-while to ensure at least one iteration

Understanding the Wrap-Around Logic

Sorted circular list: [3, 4, 1] → 1 points to 3

When curr = 4, curr->next = 1:
  - We're at the wrap point (largest → smallest)
  - insertVal = 2: insertVal >= 4? No, insertVal <= 1? No → continue
  - insertVal = 5: insertVal >= 4? Yes → insert here
  - insertVal = 0: insertVal <= 1? Yes → insert here

Implementation Details

Empty List Handling

if not head:
    new_node = Node(insertVal)
    new_node.next = new_node  # Self-referencing
    return new_node

Normal Insertion Case

# Insert between curr and curr.next
if curr.val <= insertVal <= curr.next.val:
    new_node = Node(insertVal, curr.next)
    curr.next = new_node
    return head

Wrap-Around Insertion Case

# At the wrap point (largest to smallest)
if curr.next.val < curr.val:
    # Insert if value is larger than max OR smaller than min
    if insertVal >= curr.val or insertVal <= curr.next.val:
        pass  # Insert here

Edge Cases

  1. Empty List: Create a circular list with single node
  2. Single Node: Insert anywhere (trivially maintains order)
  3. All Same Values: Insert at any position
  4. Insert at Head: Special care needed for wrap logic
  5. Insert Largest Value: Should go after maximum node
  6. Insert Smallest Value: Should go before minimum node

Follow-up Questions

  • What if the list is not guaranteed to be sorted?
  • How would you handle duplicate insertion values?
  • What if you need to insert multiple values at once?
  • How would you delete a value from a circular list?

Optimization Techniques

  1. Single Pass: Most efficient with O(n) time
  2. Early Exit: Return immediately after insertion
  3. Edge Case Handling: Handle empty list, single node separately
  4. Wrap Detection: Identify wrap point by comparing adjacent values

Code Quality Notes

  1. Readability: Clear variable names and logic separation
  2. Correctness: Handles all edge cases properly
  3. Performance: Optimal O(n) time complexity
  4. Memory: O(1) space complexity

This problem demonstrates sophisticated circular list manipulation and requires careful handling of wrap-around cases and edge conditions.