Problem statement

https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/

Solution

We just need to iterate our circled list with two adjacent pointers, but there can be different cases:

  1. List is empty
  2. We found place, where val in between two nodes in ascending order, e.g 3 and 8, and our val is 5.
  3. Next node is more than previous node (e.g 7 and 4, but new node we want to insert is more than 7 or less than 4, then we can insert it here.
  4. We move our pointers and if it happen that we reached head once again it means that we make full loop and we also break: in this case all values of our list are equal.

Finally, we insert our new node between two found nodes.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def insert(self, head, val):
        node = Node(val, head)
        if not head: 
            node.next = node
            return node   #case 1
        prev, cur = head, head.next
        while True:
            if prev.val <= val <= cur.val:  #case 2
                break

            elif prev.val > cur.val and not cur.val <= val <= prev.val:  #case 3
                break

            prev, cur = prev.next, cur.next
            if prev == head: #case 4
                break
                
        prev.next = node
        node.next = cur
        return head