/*
Given a pointer to a node in a sorted circular singly linked list( sorted in ascending order), write a function to insert a value K into the list such that the linked list still remains a sorted circular list.


Note1: If the given pointer is null i.e. empty list, create a circular list with a new node and return the reference to the new node. Otherwise,return the initial input pointer given.


Note2: The list could have duplicate values. You can insert the new value in any place which will keep the list sorted.

Input Format
First line contains N, the number of nodes in the linked list.

The next line contains N space-separated integers, representing the nodes of the circular linked list.

The last line contains a single integer K, denoting the value that is to be inserted.

Output Format
Return the original pointer given as an argument, after modifying the list by inserting the value. The output prints the modified linked list starting from the returned node.

Constraints
0 <= N <= 10^5

0 <= value <= 10^9

0 <= K <= 10^9

Sample Input 1
7

4 5 9 10 0 1 2

7

Sample Output 1
4 5 7 9 10 0 1 2

Explanation 1
The input is a sorted circular linked list and the given pointer is a reference to node [4]. A new node with [7] has to be inserted between [5] and [9] for the list to remain sorted. Return node [4] which is the input pointer given.

Sample Input 2
0

4

Sample Output 2
4

Explanation 2
The input is a sorted circular linked list which is empty. Create a circular linked list with a new node [4] and return the new node.
*/

/*
class ListNode{
    constructor(val){
        this.val = val;
        this.next = null;
    }
*/
/**
 * @param {ListNode} head
 * @param {number} insertVal
 * @return {ListNode}
 */

/*The approach you've described is for performing a sorted insert into a circular linked list. Let's break down each case and provide some intuition for each scenario:

**1) Linked List is empty:**
   - In this case, you are inserting a new node into an empty circular linked list.
   - You create a new node (`new_node`) and make it point to itself, creating a self-loop.
   - You then update the head pointer to point to the new node, making it the only node in the list.
   - Intuition: Since the list is empty, the new node becomes both the first and last node in the circular list, and it points to itself.

**2) New node is to be inserted just before the head node:**
   - Here, you want to insert a new node just before the current head node.
   - You need to find the last node in the circular list, which can be done by traversing the list until you encounter the node whose `next` points to the current head.
   - You update the `next` of the last node to point to the new node, effectively connecting the last node to the new node.
   - You then update the `next` of the new node to point to the current head, making it the new head.
   - Intuition: You are essentially moving the head to the new node and connecting the last node to it, creating a new circular arrangement.

**3) New node is to be inserted somewhere after the head:**
   - In this case, you want to insert a new node somewhere after the current head node while maintaining the sorted order.
   - You start by traversing the list until you find the node after which you want to insert the new node. This involves checking the value of the `next` node in the traversal.
   - Once you've found the appropriate insertion point, you update the `next` of the new node to point to the node that came after it.
   - Then, you update the `next` of the node you found in the traversal to point to the new node, effectively inserting it into the list.
   - Intuition: You are finding the correct position for insertion and adjusting the pointers of the surrounding nodes to include the new node while maintaining the sorted order.

In all cases, the key is to manipulate the `next` pointers of the nodes to insert the new node correctly and maintain the circular structure of the linked list. The approach ensures that the list remains sorted after the insertion. */
function insertIntoSortedCircularList(head, insertVal) {
    let newNode=new ListNode(insertVal);
    let curr=head;
    let prev=null;
    // if list is empty
    if(head==null)
    {
        newNode.next=newNode;
        head=newNode;
        return head;
    }

    // if newnode is to be inserted at front of cll
    else if(curr.val>=insertVal){
        while(curr.next!=head){
                curr=curr.next;
        }
        curr.next=newNode;
        newNode.next=head;
        head=newNode;
        return head
    }
    else{
        //  if newnode is to be inserted somewhere in between the CLL
        let prev=null;
        while(curr.next!=head&&curr.val<=insertVal){
            prev=curr;
            curr=curr.next;
        }
        // check if newNode is to be inserted at the end
            newNode.next=prev.next;
            prev.next=newNode;

        return head;
    }

    return head;


}