Insert into a Sorted Circular Linked List

Medium

Insert into a Sorted Circular Linked List

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the linked list and for insertVal?
Can the input list be empty? If so, what value should the newly created node point to?
If there are duplicate values in the sorted circular linked list, where should the new node be inserted relative to those duplicates (before, after, or either)?
If insertVal is smaller than all values or larger than all values in the list, where should the new node be inserted?
Is the linked list guaranteed to be valid and circular before the insertion? (e.g., no broken links, a proper cycle)

Brute Force Solution

Approach

The brute force method involves checking all possible insertion points within the circular sorted list to find the correct location for the new value. We essentially try every single position to see where the value fits according to the sorted order. This is like trying to fit a puzzle piece in every possible spot until you find the right one.

Here's how the algorithm would work step-by-step:

Start by examining the current node's value in the circular list.
Check if the new value should be inserted right before or after the current node, maintaining the sorted order of the circular list. Think about if the new value is bigger or smaller.
If the new value doesn't belong there, move to the next node in the circular list and repeat the comparison.
Keep going around the entire circular list, checking each position.
Eventually, you will find a spot where inserting the new value maintains the sorted order of the circular list. Insert the new value at that spot.
After inserting the new value, make sure the circular list is still properly connected.

Code Implementation

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

def insert_into_sorted_circular_linked_list(head, insert_value):
    new_node = Node(insert_value)

    if not head:
        new_node.next = new_node
        return new_node

    current_node = head

    while True:
        # Check if the new value fits between current and next node
        if (current_node.data <= insert_value <= current_node.next.data) or \
           (current_node.data > current_node.next.data and \
            (insert_value >= current_node.data or insert_value <= current_node.next.data)):

            new_node.next = current_node.next
            current_node.next = new_node
            return head

        #Handles case where the list has a single repeating value
        if current_node.data == current_node.next.data and current_node.next == head:

            new_node.next = current_node.next
            current_node.next = new_node
            return head

        current_node = current_node.next

        # Traverse the list once to find the insertion point
        if current_node == head:

            #Insert at the end if value is the list max or min
            new_node.next = current_node.next
            current_node.next = new_node
            return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the circular linked list to find the correct insertion point. In the worst-case scenario, it might need to traverse the entire list once before finding the appropriate position. Since we are visiting each node at most once, the time complexity is directly proportional to the number of nodes (n) in the list. Thus, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm for inserting into a sorted circular linked list operates in-place, modifying the existing list structure directly. It only requires a constant amount of extra space to store a pointer to the new node being inserted and possibly a pointer to traverse the list. No auxiliary data structures like arrays, hash maps, or recursion stacks are utilized. Therefore, the space complexity is independent of the size (N) of the linked list and remains constant.

Optimal Solution

Approach

The goal is to find the correct spot to insert a new number into a sorted circle of numbers. We need to handle cases where the new number fits within the existing sorted order, and also cases where it should be the new minimum or maximum value in the circle.

Here's how the algorithm would work step-by-step:

First, if the circle is empty, create a new circle with only the new number in it and point it to itself.
If the circle is not empty, start at any point in the circle.
Move around the circle, checking if the new number belongs between the current number and the next number.
If you find such a spot, insert the new number there.
If you go all the way around the circle without finding a suitable spot, it means the new number is either the new smallest or largest in the circle. In this case, insert the new number after the largest number in the original circle.

Code Implementation

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

def insert_into_sorted_circular_linked_list(head, insert_value):
    new_node = Node(insert_value)

    if not head:
        new_node.next = new_node
        return new_node

    current_node = head

    while True:
        next_node = current_node.next

        # Check if the new node belongs between current and next.
        if (current_node.data <= insert_value <= next_node.data) or \
           (current_node.data > next_node.data and \
            (insert_value >= current_node.data or insert_value <= next_node.data)):
            new_node.next = next_node
            current_node.next = new_node
            return head

        current_node = next_node

        # If we've traversed the entire list.
        if current_node == head:
            
            #Insert at the end if it's the new maximum.
            new_node.next = next_node
            current_node.next = new_node
            return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the circular linked list at most once to find the correct insertion point for the new value. In the worst-case scenario, the algorithm traverses the entire list to determine that the new value should be inserted as the new minimum or maximum element. Therefore, the time complexity is directly proportional to the number of nodes (n) in the list, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm operates directly on the existing circular linked list and only creates a single new node for the insertion. It doesn't use any auxiliary data structures like arrays, hash maps, or recursion. The space required is constant regardless of the number of nodes, N, in the original list.

Edge Cases

Case	How to Handle
Empty list (head is null)	Create a new circular linked list with the insertVal and return its head.
List with only one node	Insert the new node after the existing node, making it a circular list.
insertVal is smaller than the smallest value in the list	Insert the node before the smallest value (likely right after the largest value).
insertVal is larger than the largest value in the list	Insert the node after the largest value (likely before the smallest value).
insertVal falls between two existing values	Traverse the list and insert the node in the correct sorted position between the two values.
All values in the list are the same and insertVal is equal to them	Insert the node after any existing node as the list is already sorted.
All values in the list are the same and insertVal is different	Insert the node after any node, maintaining circularity.
Very large list impacting performance	The solution should have linear time complexity O(n) as it might need to traverse the entire list in the worst case.