---
tags: leetcode
---

# [708. Insert into a Sorted Circular Linked List](https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

/*
// 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) {
        if (head == nullptr) {
            head = new Node(insertVal);
            head->next = head;
            return head;
        }

        Node *curr = head, *prev = head->next;
        do {
            if (prev->val >= curr->val) {
                if (curr->val <= insertVal && insertVal <= prev->val) {
                    Node *newNode = new Node(insertVal);
                    newNode->next = prev;
                    curr->next = newNode;
                    return head;
                }
            } else {
                // curr points to the node with the largest value.
                // prev points to the node with the smallest value.
                // prev->val < curr->val
                if (curr->val <= insertVal || insertVal <= prev->val) {
                    Node *newNode = new Node(insertVal);
                    newNode->next = prev;
                    curr->next = newNode;
                    return head;
                }
            }
            curr = curr->next;
            prev = prev->next;
        } while (curr != head);

        Node *newNode = new Node(insertVal);
        newNode->next = prev;
        curr->next = newNode;
        return head;
    }
};

## Time Complexity
$O(n)$
$n$ is the number of nodes in the circular linked list.
## Space Complexity
$O(1)$
# Miscellaneous
<!--
# Test Cases

[3,4,1]
2

[]
1

[1]
0

[3,3,3]
0

[3,3,3]
3

[5,1,3]
3

[3,3,3]
4

[3,3,3]
2

* Wrong Answer:

[3,5,1]
0

-->