We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Insert into a Sorted Circular Linked List

Number: 850

Difficulty: Medium

Paid? Yes

Companies: Meta, Google, Anduril, Amazon, TikTok

Problem Description

Given a circular linked list where the nodes are sorted in non-descending order, insert a new value into the list so that the list remains sorted. The given node may not be the smallest. Return the original node (or the new node if the list was empty), ensuring the circular order is maintained.

Key Insights

  • Handle the empty list edge-case by creating a new node that points to itself.
  • Traverse the list until the proper insertion point is found.
  • Consider the "turning point" where the maximum value is followed by the minimum value.
  • If no proper place is found in one full rotation, insert the new node arbitrarily (e.g., after the head).

Space and Time Complexity

Time Complexity: O(n) in the worst-case when a full loop is required. Space Complexity: O(1) since we only use a few extra pointers.

Solution

We traverse the circular linked list starting from the arbitrary given node. For each pair of consecutive nodes (curr and next), we check if the new value can be inserted between them by confirming that:

  • The new value lies between curr and next (curr.val ≤ insertVal ≤ next.val).
  • Or if we are at the pivot point where the maximum value meets the minimum value (i.e., curr.val > next.val) and then either the new value is larger than or equal to curr.val (should be appended after the maximum) or less than or equal to next.val (should be inserted before the minimum).

If no proper spot is found after one complete loop, we insert anywhere (all values in the list are the same). A pointer reference is updated accordingly to maintain the circular structure.

Code Solutions

# Definition for a Node.
class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        # If the list is empty, create a new node pointing to itself and return it.
        if not head:
            newNode = Node(insertVal)
            newNode.next = newNode
            return newNode
        
        curr = head
        inserted = False
        
        while True:
            # Case 1: insert between two nodes where insertVal is between curr.val and curr.next.val.
            if curr.val <= insertVal <= curr.next.val:
                inserted = True
            # Case 2: curr.val > curr.next.val, i.e., we are at the turning point.
            # In this case, insert if insertVal is greater than curr.val (largest)
            # or insertVal is less than curr.next.val (smallest).
            elif curr.val > curr.next.val:
                if insertVal >= curr.val or insertVal <= curr.next.val:
                    inserted = True
            
            if inserted:
                newNode = Node(insertVal, curr.next)
                curr.next = newNode
                return head
            
            curr = curr.next
            # If we have traversed the entire circle and came back to head, break.
            if curr == head:
                break
        
        # Case 3: All values are the same or no valid index was found, insert arbitrarily.
        newNode = Node(insertVal, curr.next)
        curr.next = newNode
        return head
← Back to All Questions