Sorted Insert For Circular Linked List

Problem Link

Sorted insert for circular linked list – GFG

Problem Statement

Given a sorted circular linked list and a data value, the task is to insert this data in a sorted way into the circular linked list.

Examples

Example 1:

Input:
LinkedList = 1->2->4 (circular)
data = 2
Output:
1 2 2 4

Example 2:

Input:
LinkedList = 1->4->7->9 (circular)
data = 5
Output:
1 4 5 7 9

Constraints

• The linked list is sorted in increasing order

• The list is circular, i.e., the last node points back to the head

• 1 <= N <= 100 (N = number of nodes)

Intuition

Since the list is circular and sorted, we need to:

• Traverse the list to find the appropriate position to insert the new node.

• Take care of two special cases:

  1. When the new node has to be inserted before the head (new smallest element)

  2. When the list has only one node

Approach

1. Create a new node with the given data.

2. Handle the base case: if the list is empty, make the new node point to itself and return.

3. Handle the case where the new node should be inserted before the head (new smallest value).

4. Otherwise, traverse the list to find the appropriate insertion point.

5. Insert the node by updating the .next pointers.

Java Code

class Solution {
    public Node sortedInsert(Node head, int data) {
        Node newNode = new Node(data);
        
        // Case 1: Empty list
        if (head == null) {
            newNode.next = newNode;
            return newNode;
        }
        
        Node curr = head;

        // Case 2: Insert before head (new node is smallest)
        if (data <= head.data) {
            while (curr.next != head) {
                curr = curr.next;
            }
            curr.next = newNode;
            newNode.next = head;
            return newNode; // new head
        }

        // Case 3: Insert somewhere after head
        while (curr.next != head && curr.next.data < data) {
            curr = curr.next;
        }

        newNode.next = curr.next;
        curr.next = newNode;
        return head;
    }
}

Time and Space Complexity

Dry Run

Input:

head = 1 → 2 → 4 → back to 1
data = 3

• New node = 3

• Traverse:

  • 1 < 3 → move

  • 2 < 3 → move

  • 4 > 3 → stop

• Insert new node between 2 and 4

Output: 1 → 2 → 3 → 4 → back to 1

Conclusion

This problem reinforces pointer manipulation and edge case handling in circular linked lists.
Always consider empty list and insert-before-head scenarios when dealing with circular structures.