1. Two-Pointers Iteration

Intuition

In a sorted circular linked list, we need to find the right spot to insert while maintaining sorted order. There are three cases to consider: the value fits between two existing nodes, the value is a new maximum or minimum (insert at the tail/head boundary), or all nodes have the same value.
We use two pointers to traverse the list, looking for the gap where our value belongs. The tail-to-head boundary is special because it's where the values wrap around from largest to smallest.
If we traverse the entire list without finding a spot, it means all values are equal, so we can insert anywhere.

Algorithm

  1. If the list is empty, create a new node pointing to itself and return it.
  2. Initialize prev to head and curr to head.next. Use a flag toInsert to track when we find the insertion point.
  3. Traverse the list:
    • Case 1: If prev.val <= insertVal <= curr.val, we found a normal insertion point between two nodes.
    • Case 2: If prev.val > curr.val, we're at the tail-to-head boundary. Insert here if insertVal >= prev.val (new maximum) or insertVal <= curr.val (new minimum).
    • If either case is true, insert the new node between prev and curr and return head.
  4. Move the pointers forward. If we return to the starting position without inserting, insert the node anywhere (Case 3: all values are equal).
class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':

        if head == None:
            newNode = Node(insertVal, None)
            newNode.next = newNode
            return newNode
 
        prev, curr = head, head.next
        toInsert = False

        while True:
            
            if prev.val <= insertVal <= curr.val:
                # Case #1.
                toInsert = True
            elif prev.val > curr.val:
                # Case #2. where we locate the tail element
                # 'prev' points to the tail, i.e. the largest element!
                if insertVal >= prev.val or insertVal <= curr.val:
                    toInsert = True

            if toInsert:
                prev.next = Node(insertVal, curr)
                # mission accomplished
                return head

            prev, curr = curr, curr.next
            # loop condition
            if prev == head:
                break
        # Case #3.
        # did not insert the node in the loop
        prev.next = Node(insertVal, curr)
        return head

Time & Space Complexity

  • Time complexity: O(N)O(N)
  • Space complexity: O(1)O(1)

Where NN is the size of the list.