Inserting A Node In A Sorted Circular Singly Linked List

This is a popular question often asked in some coding interviews, where you are given a circular linked list which is sorted and you need to insert a node so that the list remains sorted. Note that the start pointer that would be provided might not be the first element in the list (well, technically there is no first element in a circular linked list as well).

The simple approach to solving this is to traverse the list, find the minimum and maximum items. Then again traverse the list from minimum to maximum, and insert the new node at the correct position. Here you need to perform two traversals, which can be costly.

This can be optimized to only a single traversal by maintaining a separate variable to keep track of the maximum node. Simultaneously, find the correct position to enter the new node and keep a track of whether the node has been inserted or not. If not, then definitely it would be added after the maximum element which can be then be done directly. Note that this approach has a linear runtime and requires no extra space. Here's the Python3 code for the same.

    def insert(self, node, x):
        # if list is empty
        if not node:
            node = ListNode(x)
            node.next = node
            return node
        # if list not empty
        curr = maxNode = node
        newNode = ListNode(x)
        nodeInserted = False # to keep track if the newNode has been inserted or not
        while(1):
            if curr.next.val < curr.val:
                maxNode = curr
            if curr.next.val >= x and curr.val <= x:
                # insert in this gap
                newNode.next = curr.next
                curr.next = newNode
                nodeInserted = True
                break
            curr = curr.next
            if curr == node:
                break # Should not loop over more than once
        if not nodeInserted:
            # if node has still not been inserted
            # that indicates it is located at the turning point from MAX to MIN
            newNode.next = maxNode.next
            maxNode.next = newNode
            # nodeInserted = True
        return node

There is another way to preprocess the linked list and do the search even faster by exploiting the fact that it is already sorted. You need to make use of a map (ideally a TreeMap) where the keys are the node values and the values are the nodes itself. Then one can implement a binary search algorithm and perform the insertion even faster. This is a good approach with a better (logarithmic) runtime but at the cost extra space for the map.