Insert into a Sorted Circular Linked List LeetCode Solution

Table of Contents

Problem Statement:

Insert into a Sorted Circular Linked List LeetCode Solution – says that Given a Circular Linked List node, which is sorted in ascending 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:

Input:

 head = [3,4,1], insertVal = 2

Output:

 [3,4,1,2]

Explanation:

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 we should still return node 3.

Approach:

Idea:

The basic approach is to find the exact position where we need to insert the new node. We just need to keep track of what position are we inserting the new node. That is in the beginning, in the end, or in between two nodes. Here insertion at the beginning or at the end will give the same results as it is a circular linked list. Also, we need to keep track of some base cases, like if the node is NULL or we have only one node.

Code:

Insert into a Sorted Circular Linked List C++ Leetcode Solution:

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if(!head){
            head = new Node(insertVal);
            head->next = head;
            return head;
        }
        
        Node* ptr = head;
        Node* start = head;
        while(ptr->next){
            if(ptr->val > ptr->next->val){
                start = ptr->next;
                break;
            }
            if(ptr->next == head)
                break;
            ptr = ptr->next;
        }
        if(ptr==start){
            ptr->next = new Node(insertVal);
            ptr->next->next = ptr;
            return head;
        }
        Node* prev = NULL;
        int cnt=0;
        while(start){
            if(start->val>=insertVal){
                if(!prev){
                    Node* temp = head;
                    while(temp->next!=start)
                        temp = temp->next;
                    
                    temp->next = new Node(insertVal);
                    temp->next->next = start;
                    return head;
                
                }
                prev->next = new Node(insertVal);
                prev->next->next = start;
                return head;
            }
            prev = start;
            start = start->next;
            
            if(start==head)
                cnt++;
            
            if(cnt==2){
                Node* temp = ptr->next;
                ptr->next = new Node(insertVal);
                ptr->next->next = temp;
                return head;
            }
        }
        return head;
    }
};

Insert into a Sorted Circular Linked List Java Leetcode Solution:

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

Complexity Analysis of Insert into a Sorted Circular Linked List:

Time Complexity: The time complexity of the above code is $O (n)$ where n is the number of nodes in the list.
Space Complexity: The space complexity of the above code is $O (1)$ as we did not use any extra space.