708. Insert into a Sorted Circular Linked List


Problem Description

This problem involves a special kind of linked list called a Circular Linked List, where the last element points back to the first, creating a closed loop. Your task is to insert a new value into the list so that the list's non-descending (sorted) order is maintained.

The nuances of this task are:

  1. The node you are given could be any node in the loop, not necessarily the smallest value.
  2. You may insert the new value into any position where it maintains the sort order.
  3. If the list is empty (i.e., the given node is null), you must create a new circular list that contains the new value and return it.

You're expected to return a reference to any node in the modified list.

Intuition

The intuition behind the solution starts with understanding the properties of a sorted circular linked list. In such a list, values gradually increase as you traverse the list, before suddenly "resetting" to the smallest value once the loop completes.

Given these properties, the solution involves handling three distinct scenarios:

  1. The list is empty: If the list is empty, you create a new node that points to itself and return it as the new list.

  2. Normal insertion: In a populated list, you traverse the nodes looking for the right place to insert the new value. The right place would be between two nodes where the previous node's value is less than or equal to the new value, and the next node's value is greater than or equal to the new value.

  3. Edge Insertion: If you don't find such a position, it means the new value either goes before the smallest value in the list or after the largest one. This specific case occurs at the "reset" point where the last node in sort order (with the largest value) points to the first node (with the smallest value).

The algorithm involves iterating through the list, comparing the insertVal with the current and next node values to find the correct insertion point. Once found, adjust the necessary pointers to insert the new node.

We also guarantee that we loop no more than once by comparing the current node to the initial head node. If we reach the head again, it means we've checked every node, which handles cases where all nodes in the list have the same value and the insertVal could go anywhere.

So the high-level steps are:

  • Handle the edge case where the list is empty.
  • Traverse the list looking for the insertion point.
  • Insert the node when the correct spot is found.
  • If the loop completes without finding the exact position, insert the node just after the largest value or before the smallest value.

With this approach, we insert the new value while maintaining the list's sorted order.

Solution Approach

The solution implementation involves a straightforward but careful traversal of the circular linked list to maintain its sorted property after insertion.

First, we need to handle a special case:

  • Empty list: If the list is empty (head is None), we create a new node that points to itself and return it as the new list head (circular in nature).

For a non-empty list, we follow these steps:

  1. Initialize two pointers, prev and curr - starting from head and head.next respectively. We’ll move these pointers forward until we find the correct insert location.

  2. Loop through the circular list and look for the correct position to insert the insertVal. The loop will terminate if:

    • We find a spot where the value directly after prev (curr) is greater than or equal to insertVal, and the value at prev is less than or equal to insertVal. This means insertVal fits right between prev and curr.
    • We find the point where the values "reset," indicating prev holds the maximum value and curr holds the minimum value in the list. If insertVal is greater than or equal to prev.val (greater than the list's max value) or insertVal is less than or equal to curr.val (less than the list's min value), it means insertVal must be inserted here.
  3. For insertion:

    • Create a new node with insertVal.
    • Adjust the next pointer of prev to point to this new node.
    • Set the new node's next pointer to curr.
  4. Return the head of the list.

Here is the algorithm in Python code snippet from the Reference Solution Approach:

1class Node:
2    def __init__(self, val=None, next=None):
3        self.val = val
4        self.next = next
5
6class Solution:
7    def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
8        node = Node(insertVal)
9        if head is None:
10            node.next = node
11            return node
12        prev, curr = head, head.next
13        while curr != head:
14            if prev.val <= insertVal <= curr.val or (
15                prev.val > curr.val and (insertVal >= prev.val or insertVal <= curr.val)
16            ):
17                break
18            prev, curr = curr, curr.next
19        prev.next = node
20        node.next = curr
21        return head

By utilizing the Node class to instantiate the new element to be inserted and updating pointers in a singly linked list fashion, you efficiently maintain both the circular nature of the list and the sorted order with a simple yet effective algorithm that walks through the list once at most.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have a circular sorted linked list and we need to insert a value insertVal into the list. Our circular linked list is as follows:

13 -> 4 -> 1
2^         |
3|_________|

Here, 3 is the smallest element before the reset and 1 is the last element pointing back to 3. Now let's say we want to insert 5. We must find the correct spot for 2 so that the list remains sorted in non-descending order. The step will be as follows:

  1. Since the list is not empty, we initialize prev to this node (3) and curr to the next node (4).

  2. We start traversing the list. As insertVal (5) is not between 3 (prev.val) and 4 (curr.val), we move forward.

  3. Now, prev is 4 and curr is 1. We check:

    • Is 4 (prev.val) less than 5 (insertVal) and 5 (insertVal) less than 1 (curr.val)? No.
    • Does 4 (prev.val) > 1 (curr.val) indicating a reset point in the list ordering? Yes.
    • Is 5 (insertVal) >= 4 (prev.val) or 5 (insertVal) <= 1 (curr.val)? The first condition is true.
  4. We have reached the reset point of our list, and since 5 (insertVal) is less than 1 (curr.val), it must be inserted between 4 (prev) and 1 (curr).

  5. We create a new node with the value 5, update the prev.next to point to this new node, and set the new node's next pointer to curr.

Now our list looks like this:

13 -> 4 -> 5 -> 1
2^               |
3|_______________|
  1. We return the head of the list, which can be any node in the list; in this case, we still consider the node with value 3 as the head.

Through this example, we can see how the list is effectively iterated once to find the correct spot, and how the pointers are adjusted to maintain the order after insertion. The critical part of the approach is handling the edge cases where the insertVal is greater than the maximal value or smaller than the minimal value in the list.

Python Solution

1class Node:
2    def __init__(self, value=None, next_node=None):
3        self.value = value
4        self.next_node = next_node
5
6
7class Solution:
8    def insert(self, head: 'Optional[Node]', insert_value: int) -> 'Node':
9        # Create a new node with the insert_value
10        new_node = Node(insert_value)
11
12        # If the linked list is empty, initialize it with the new node
13        if head is None:
14            new_node.next_node = new_node  # Point the new_node to itself
15            return new_node
16      
17        # Initialize two pointers for iterating the linked list
18        previous, current = head, head.next_node
19
20        # Traverse the linked list
21        while current != head:
22            # Check if the insert_value should be inserted between previous and current
23            # The first condition checks for normal ordered insertion
24            # The second condition checks for insertion at the boundary of the largest and smallest values
25            if (
26                previous.value <= insert_value <= current.value or
27                (previous.value > current.value and (insert_value >= previous.value or insert_value <= current.value))
28            ):
29                break  # Correct insertion spot is found
30
31            # Move to the next pair of nodes
32            previous, current = current, current.next_node
33
34        # Insert new_node between previous and current
35        previous.next_node = new_node
36        new_node.next_node = current
37
38        # Return the head of the modified linked list
39        return head
40

Java Solution

1// Class definition for a circular linked list node
2class Node {
3    public int value;
4    public Node next;
5
6    // Constructor for creating a new node without next reference
7    public Node(int value) {
8        this.value = value;
9    }
10
11    // Constructor for creating a new node with next reference
12    public Node(int value, Node next) {
13        this.value = value;
14        this.next = next;
15    }
16}
17
18class Solution {
19    // Method to insert a node into a sorted circular linked list
20    public Node insert(Node head, int insertValue) {
21        // Create the node to be inserted
22        Node newNode = new Node(insertValue);
23
24        // If the linked list is empty, point the new node to itself and return it
25        if (head == null) {
26            newNode.next = newNode;
27            return newNode;
28        }
29
30        // Pointers for tracking the current position and the previous node
31        Node previous = head, current = head.next;
32
33        // Iterate through the list to find the insertion point
34        while (current != head) {
35
36            // Check if the new node fits between previous and current nodes
37            if ((previous.value <= insertValue && insertValue <= current.value)
38                // or if it's the end/beginning of the list,
39                // as the next value is less than the previous due to the circular nature
40                || (previous.value > current.value && (insertValue >= previous.value || insertValue <= current.value))) {
41                break; // Found the place to insert
42            }
43
44            // Move to next pair of nodes
45            previous = current;
46            current = current.next;
47        }
48
49        // Insert the new node between previous and current
50        previous.next = newNode;
51        newNode.next = current;
52
53        // Return the head of the list
54        return head;
55    }
56}
57

C++ Solution

1/*
2// Definition for a circular singly-linked list Node.
3class Node {
4public:
5    int val;      // Value of the node
6    Node* next;   // Pointer to the next node
7
8    Node() {}
9
10    Node(int value) {
11        val = value;
12        next = nullptr;
13    }
14
15    Node(int value, Node* nextNode) {
16        val = value;
17        next = nextNode;
18    }
19};
20*/
21
22class Solution {
23public:
24    Node* insert(Node* head, int insertVal) {
25        Node* newNode = new Node(insertVal); // Create a new node with the insertVal
26
27        // If the list is empty, initialize it with the new node which points to itself
28        if (!head) {
29            newNode->next = newNode; // Points to itself to maintain circularity
30            return newNode; // Return new node as the new head of the list
31        }
32
33        Node *prev = head;
34        Node *current = head->next;
35        bool inserted = false;
36
37        while (true) {
38            // Check if we have found the correct place to insert the new node
39            if ((prev->val <= insertVal && insertVal <= current->val) ||   // Case 1: Value lies between prev and current
40                (prev->val > current->val && (insertVal >= prev->val || insertVal <= current->val))) { // Case 2: At tail part after the max val or before the min val in sorted circular list
41                // Insert new node here
42                prev->next = newNode;
43                newNode->next = current;
44                inserted = true;
45                break;
46            }
47          
48            prev = current;
49            current = current->next;
50
51            // If we completed one full circle around the list and didn't insert the new node, break loop to insert at the end.
52            if (prev == head) {
53                break;
54            }
55        }
56
57        // If the new node hasn't been inserted yet, it should be placed between the tail and the head.
58        // This case also covers a list with uniform values.
59        if (!inserted) {
60            prev->next = newNode;
61            newNode->next = current;
62        }
63
64        // Return the head of the list
65        return head;
66    }
67};
68

Typescript Solution

1// Definition for a circular singly-linked list node.
2class ListNode {
3    val: number;
4    next: ListNode | null;
5
6    constructor(val?: number, next?: ListNode | null) {
7        this.val = (val === undefined ? 0 : val);
8        this.next = (next === undefined ? null : next);
9    }
10}
11
12// Function to create a new node with a given value
13function createNode(value: number): ListNode {
14    return new ListNode(value);
15}
16
17// Function to insert a new node with insertVal into the circular linked list
18function insert(head: ListNode | null, insertVal: number): ListNode | null {
19    // Create a new node with the insertVal
20    const newNode = createNode(insertVal);
21
22    // If the list is empty, initialize it with the new node which points to itself
23    if (head === null) {
24        newNode.next = newNode; // Points to itself to maintain circularity
25        return newNode; // Return new node as the new head of the list
26    }
27
28    let prev = head;
29    let current = head.next;
30    let inserted = false;
31
32    do {
33        // Check if we have found the correct place to insert the new node
34        // Case 1: Value lies between prev and current
35        // Case 2: At tail part after the max val or before the min val in sorted circular list
36        if ((prev.val <= insertVal && insertVal <= current.val) ||
37            (prev.val > current.val && (insertVal >= prev.val || insertVal <= current.val))) {
38            // Insert new node here
39            prev.next = newNode;
40            newNode.next = current;
41            inserted = true;
42            break;
43        }
44
45        prev = current;
46        current = current.next;
47
48        // If we completed one full circle around the list and didn't insert the new node, break loop to insert at the end.
49    } while (prev !== head);
50
51    // If the new node hasn't been inserted yet, it should be placed between the tail and the head.
52    // This case also covers a list with uniform values.
53    if (!inserted) {
54        prev.next = newNode;
55        newNode.next = current;
56    }
57
58    // Return the head of the list
59    return head;
60}
61

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the circular linked list. This complexity arises because in the worst-case scenario, the code would iterate through all the elements of the linked list once to find the correct position to insert the new value. The while loop continues until it returns to the head, meaning it could traverse the entire list.

Space Complexity

The space complexity of the given code is O(1). The only extra space used is for creating the new node to be inserted, and no additional space that grows with the size of the input linked list is used.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫