708. Insert into a Sorted Circular Linked List - Solution

The problem

Given a Circular Linked List node, which is sorted in non-descending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.

If the list is empty (i.e., the given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.

Example 1:

Input: head = [3,4,1], insertVal = 2
Output: [3,4,1,2]
Explanation: In the figure above, there is a sorted circular list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list. The new node should be inserted between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.

Example 2:

Input: head = [], insertVal = 1
Output: [1]
Explanation: The list is empty (given head is null). We create a new single circular list and return the reference to that single node.

Example 3:

Input: head = [1], insertVal = 0
Output: [1,0]

Constraints:

The number of nodes in the list is in the range [0, 5 * 10⁴].
-10⁶ <= Node.val, insertVal <= 10⁶

Approach overview

Problem Overview: You receive a reference to any node in a sorted circular linked list and a value to insert. The task is to insert a new node so the list remains sorted while preserving the circular structure.

This problem tests careful pointer traversal in a linked list where the head is not guaranteed to be the smallest element. Because the list is circular, traversal can start from any node and must detect the correct insertion window.

Approach 1: Linear Scan with Sorted Insertion (O(n) time, O(1) space)

Traverse the circular list using two pointers: curr and next. For each pair of nodes, check whether the new value belongs between them. The typical condition is curr.val ≤ insertVal ≤ next.val. Another critical case occurs at the rotation point where the maximum value connects back to the minimum (curr.val > next.val). If the value is larger than the current maximum or smaller than the minimum, insert at this boundary.

If you complete a full cycle without finding a suitable spot, all nodes contain the same value or the value fits anywhere. Insert the new node after the current node. This approach performs a single pass through the list and only updates pointers, giving O(n) time and O(1) extra space.

Approach 2: Find Rotation Pivot then Insert (O(n) time, O(1) space)

Another way to reason about the list is to first locate the pivot where the sorted order breaks (curr.val > next.val). This point separates the maximum and minimum elements. After identifying the pivot, treat next as the logical head of a sorted list and insert the new value using a standard sorted insertion scan.

This approach separates the problem into two clearer phases: identifying the boundary and inserting in order. The time complexity remains O(n) with O(1) space because the list is scanned at most once or twice. It can be easier to reason about during debugging.

Approach 3: Convert to Array, Insert, Rebuild (O(n) time, O(n) space)

A brute-force strategy converts the circular list into an array by traversing until you return to the starting node. Insert the value into the sorted array using binary search or linear insertion, then rebuild the circular linked list.

This method simplifies reasoning but wastes memory and loses the advantage of pointer-based operations. It runs in O(n) time and O(n) space. Interviewers rarely expect this solution but it can help verify logic when first approaching circular structures.

Recommended for interviews: The linear scan insertion approach is the expected solution. It demonstrates that you understand circular traversal, boundary conditions, and pointer manipulation in circular linked lists. Explaining the rotation-point case (max → min) clearly usually matters more than the code itself.

Solution

Python

"""
# 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':
        node = Node(insertVal)
        if head is None:
            node.next = node
            return node
        prev, curr = head, head.next
        while curr != head:
            if prev.val <= insertVal <= curr.val or (
                prev.val > curr.val and (insertVal >= prev.val or insertVal <= curr.val)
            ):
                break
            prev, curr = curr, curr.next
        prev.next = node
        node.next = curr
        return head

Java

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        if (head == null) {
            node.next = node;
            return node;
        }
        Node prev = head, curr = head.next;
        while (curr != head) {
            if ((prev.val <= insertVal && insertVal <= curr.val)
                || (prev.val > curr.val && (insertVal >= prev.val || insertVal <= curr.val))) {
                break;
            }
            prev = curr;
            curr = curr.next;
        }
        prev.next = node;
        node.next = curr;
        return head;
    }
}

C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node* node = new Node(insertVal);
        if (!head) {
            node->next = node;
            return node;
        }
        Node *prev = head, *curr = head->next;
        while (curr != head) {
            if ((prev->val <= insertVal && insertVal <= curr->val) || (prev->val > curr->val && (insertVal >= prev->val || insertVal <= curr->val))) break;
            prev = curr;
            curr = curr->next;
        }
        prev->next = node;
        node->next = curr;
        return head;
    }
};

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

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

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Linear Scan with Sorted Insertion	O(n)	O(1)	General case and expected interview solution
Find Rotation Pivot then Insert	O(n)	O(1)	When separating pivot detection makes reasoning clearer
Convert to Array and Rebuild	O(n)	O(n)	Conceptual or debugging approach when pointer logic is difficult

Frequently asked questions

Is Insert into a Sorted Circular Linked List easy or hard?

Insert into a Sorted Circular Linked List is generally classified as a Medium difficulty problem. The challenge comes from handling circular traversal and correctly detecting the boundary between the maximum and minimum elements.

Insert into a Sorted Circular Linked List Python/Java solution

The Python and Java implementations use the same logic: iterate through the circular list and check insertion conditions between curr and next nodes. Once the correct position is found, create a new node and update curr.next and newNode.next pointers. The implementation runs in O(n) time and O(1) space.

How to solve Insert into a Sorted Circular Linked List in O(n)?

Start from any node and traverse the circular list using two pointers, curr and next. Insert when the value falls between them in sorted order, or when you reach the rotation boundary where curr.val > next.val and the value is either larger than the max or smaller than the min. If a full cycle completes without insertion, add the node anywhere because all values are equal.

What is the best approach for Insert into a Sorted Circular Linked List?

The best approach is a single-pass linear traversal that checks where the new value fits between two adjacent nodes. You insert when curr.val ≤ insertVal ≤ next.val or when you detect the rotation point where the maximum value connects to the minimum. This solution runs in O(n) time and uses O(1) extra space.

Is Insert into a Sorted Circular Linked List asked at Google/Amazon/Meta?

Circular linked list manipulation problems frequently appear in interviews at companies like Meta, Amazon, and Google. Variants test your ability to handle pointer traversal, detect rotation points, and maintain sorted order in non-linear list structures.

What data structure is used in Insert into a Sorted Circular Linked List?

The problem uses a circular singly linked list where the last node points back to the first node. Operations involve pointer traversal and insertion while preserving sorted order across the circular boundary.

What is the time complexity of Insert into a Sorted Circular Linked List?

The optimal solution runs in O(n) time because you may need to traverse the entire circular list once to find the correct insertion point. Space complexity is O(1) since the algorithm only updates node pointers without using additional data structures.

Insert into a Sorted Circular Linked List solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Insert into a Sorted Circular Linked List solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems