LeetCode 708 - Insert into a Sorted Circular Linked List

Difficulty: 🟡 Medium
Topics: Linked List

Solution

Let's go step by step and create a complete technical solution guide for LeetCode 708 - Insert into a Sorted Circular Linked List following your formatting requirements.

Problem Understanding

The problem asks us to insert a value into a sorted circular linked list such that the list remains sorted. A circular linked list is a linked list where the last node points back to the first node, creating a cycle. The list is sorted in non-descending order, but the given reference node is not guaranteed to be the smallest.

The input is a reference to any node in the circular list (or null if the list is empty) and an integer insertVal. The output should be the same reference node (or a new node if the list was empty), with the new value correctly inserted.

Constraints and important considerations: the list may be empty, may have only one node, or may have multiple nodes. Node values can be negative or positive. Multiple valid insertion points may exist due to circularity and duplicate values. The solution must handle all these cases correctly.

Important edge cases include: inserting into an empty list, inserting a value smaller than all existing nodes, inserting a value larger than all existing nodes, and inserting into a list where all node values are equal.

Approaches

Brute Force Approach

A naive solution is to traverse the circular list node by node and check every pair of consecutive nodes to find where the new value should go. The value should be inserted between curr and curr.next if it is between their values.

In a circular list, if the list wraps from the largest back to the smallest value, we can insert the new value if it is larger than the max or smaller than the min, which is when curr.val > curr.next.val.

This approach works, but it requires traversal in the worst case of the entire list to find the correct insertion point. While functional, it can be optimized in readability and handling edge cases elegantly.

Optimal Approach

The key observation is that in a sorted circular list, there are only two main conditions for insertion:

The new value falls between two nodes in ascending order (curr.val <= insertVal <= curr.next.val).
The new value is either larger than the current max or smaller than the current min (the transition point where curr.val > curr.next.val).

By detecting these conditions while traversing, we can find a proper insertion point in one pass, even if the list is circular or contains duplicates. If no condition matches after a full cycle, all nodes are equal, and we can insert anywhere, such as right after the starting node.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Traverse entire list to find insertion; works but verbose
Optimal	O(n)	O(1)	Single-pass insertion using two conditions; handles all edge cases

Algorithm Walkthrough

If the input node head is None, create a new node with insertVal and point it to itself. Return this node.
Initialize a pointer curr to head.
Loop indefinitely, checking consecutive nodes curr and curr.next. There are three insertion conditions:

a. If curr.val <= insertVal <= curr.next.val, insert here.

b. If curr.val > curr.next.val (the transition from max to min) and (insertVal >= curr.val or insertVal <= curr.next.val), insert here.

c. If we return to the starting node without finding a suitable place (all values equal), insert after curr. 4. To insert, create a new node with insertVal, set its next to curr.next, and then update curr.next to the new node. 5. Return the original head.

Why it works:

The algorithm maintains the invariant that the list is circular and sorted. By checking both normal ascending order and the max-to-min transition, we guarantee that the insertion preserves order. The fallback ensures insertion even if all values are equal.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
        if not head:
            new_node = Node(insertVal)
            new_node.next = new_node
            return new_node
        
        curr = head
        while True:
            if curr.val <= insertVal <= curr.next.val:
                # Normal case: value fits between two nodes
                break
            if curr.val > curr.next.val:
                # Transition from max to min
                if insertVal >= curr.val or insertVal <= curr.next.val:
                    break
            curr = curr.next
            if curr == head:
                # Completed full cycle without break; insert anywhere
                break
        
        new_node = Node(insertVal, curr.next)
        curr.next = new_node
        return head

Explanation:

The code first handles the empty list by creating a self-referencing node. Then it traverses the circular list checking for the two insertion conditions. If no condition matches after a full cycle, the new node is inserted after the starting node. This handles duplicates and ensures the list remains circular.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 * }
 */

func insert(head *Node, insertVal int) *Node {
    if head == nil {
        newNode := &Node{Val: insertVal}
        newNode.Next = newNode
        return newNode
    }
    
    curr := head
    for {
        if curr.Val <= insertVal && insertVal <= curr.Next.Val {
            break
        }
        if curr.Val > curr.Next.Val {
            if insertVal >= curr.Val || insertVal <= curr.Next.Val {
                break
            }
        }
        curr = curr.Next
        if curr == head {
            break
        }
    }
    
    newNode := &Node{Val: insertVal, Next: curr.Next}
    curr.Next = newNode
    return head
}

Explanation:

The Go solution is structurally identical to the Python version. Nil checks are explicit for empty lists. Go pointers naturally handle the circular reference. The logic for traversal and insertion mirrors Python, with careful attention to curr == head to detect a full cycle.

Worked Examples

Example 1: `head = [3,4,1]`, `insertVal = 2`

Step	curr.val	curr.next.val	Condition met?	Action
1	3	4	3 <= 2 <= 4? No	Move to next
2	4	1	4 > 1 and 2 <= 1 or 2 >= 4? No	Move to next
3	1	3	1 <= 2 <= 3? Yes	Insert between 1 and 3

Result: [3,4,1,2]

Example 2: `head = []`, `insertVal = 1`

Empty list → create Node(1) pointing to itself. Result: [1].

Example 3: `head = [1]`, `insertVal = 0`

Single-node list → 1 > 1? No, full cycle completed → insert after 1. Result: [1,0].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Traverse at most all nodes once in circular list
Space	O(1)	Constant space for pointers and new node

The algorithm is efficient because it traverses at most once and uses no extra data structures.

Test Cases

# Empty list
assert Solution().insert(None, 1).val == 1  # creates a single-node circular list

# Single-node list
node = Node(1)
node.next = node
head = Solution().insert(node, 0)
assert head.next.val == 0  # inserted correctly

# Multi-node, normal insertion
head = Node(3, Node(4, Node(1))))
head.next.next.next = head
head = Solution().insert(head, 2)
assert head.next.next.next.val == 2

# Insert max value
head = Node(1, Node(3, Node(5))))
head.next.next.next = head
head = Solution().insert(head, 6)
assert head.next.next.next.next.val == 6

# Insert min value
head = Node(2, Node(3, Node(4))))
head.next.next.next = head
head = Solution().insert(head, 1)
assert head.next.next.next.next.val == 1

# All equal nodes
head = Node(2, Node(2, Node(2))))
head.next.next.next = head
head = Solution().insert(head, 2)
assert head.next.next.next.next.val == 2

Test	Why
Empty list	Validate creation of new circular node
Single-node	Ensure insertion after single node works
Multi-node normal	Check insertion between nodes
Insert max	Value larger than all nodes
Insert min	Value smaller than all