Insert Into A Sorted Circular Linked List - Leetcode Solution

Problem Statement:

Given a sorted circular linked list, insert a new node into the list and return the modified list.

Input:

• The head pointer of a sorted circular linked list.
• An integer val to be inserted into the list.

Output:

• The head pointer of the modified circular linked list.

Solution:

A sorted circular linked list means that the last node in the list is connected to the first node. However, we cannot traverse the whole list in a circular manner as we need to insert the new node in its proper place. Therefore, we can find the last node of the list and check whether the new node should be placed before the first node or after the last node.

Here's the algorithm to solve this problem:

1. Check if the head pointer is null or not. If it is null, create a new node with the given value and return it as the head of the list.
2. Traverse the list until the node with the largest value smaller than val is found. We can stop at this node as we know that the new node should be inserted after it.
3. Create a new node with the given value.
4. Connect the new node to the next node of the found node, which becomes the new node's next.
5. Connect the found node to the new node, which becomes the found node's next.
6. If the new node's value is smaller than the found node's value, update the head pointer to the new node.

Here is the pseudo-code to implement the above algorithm:

insertSortedCircularList(head, val):
    if head == null:
        return new ListNode(val)
    
    prev, cur = head, head.next
    while cur != head:
        if prev.val <= val <= cur.val:
            break
        if prev.val > cur.val and (val < cur.val or val > prev.val):
            break
        prev, cur = cur, cur.next
    
    newNode = ListNode(val)
    newNode.next = cur
    prev.next = newNode
    
    if val < head.val:
        return newNode
    return head

Time Complexity:

The time complexity of this solution is O(N), where N is the number of nodes in the linked list. It is because we traverse the entire list in the worst-case scenario.

Space Complexity:

The space complexity of this solution is O(1) because we are not using any additional space to store data. We are only creating a new node, so the space required for the new node is constant.

1