> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Insert into a Sorted Circular Linked List

> Tested Python solution for LeetCode 708 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 708, [Medium](/catalog/medium). Topics: [Linked List](/catalog/topics/linked-list). [View on LeetCode](https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 708   # by problem number
lcpy gen -s insert_into_a_sorted_circular_linked_list   # by problem name
```

## 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.

### Examples

```
Input: head = [3,4,1], insertVal = 2
Output: [3,4,1,2]
Explanation: The new node should be inserted between node 1 and node 3, and we should still return node 3.
```

```
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.
```

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

### Constraints

* The number of nodes in the list is in the range \[0, 5 \* 10^4].
* -10^6 \<= Node.val, insertVal \<= 10^6

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/insert_into_a_sorted_circular_linked_list/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/insert_into_a_sorted_circular_linked_list/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations


class Node:
    def __init__(self, val: int = 0, next: Node | None = None) -> None:
        self.val = val
        self.next: Node = next if next is not None else self


class Solution:
    # Time: O(n)
    # Space: O(1)
    def insert(self, head: Node | None, insert_val: int) -> Node:
        node = Node(insert_val)
        if head is None:
            return node
        prev, curr = head, head.next
        while curr is not head:
            if prev.val <= insert_val <= curr.val or (
                prev.val > curr.val and (insert_val >= prev.val or insert_val <= curr.val)
            ):
                break
            prev, curr = curr, curr.next
        prev.next = node
        node.next = curr
        return head
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.