Given a sorted circular linked list, the task is to insert a new node in this circular list so that it remains a sorted circular linked list.
Example 1:
Input:
LinkedList = 1->2->4
(the first and last node is connected,
i.e. 4 --> 1)
data = 2
Output: 1 2 2 4
Example 2:
Input:
LinkedList = 1->4->7->9
(the first and last node is connected,
i.e. 9 --> 1)
data = 5
Output: 1 4 5 7 9
Your Task:
The task is to complete the function sortedInsert() which should insert the new node into the given circular linked list and return the head of the linkedlist.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
0 <= N <= 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



'''

class Node: 

    # Constructor to initialize the node object 

    def __init__(self, data): 

        self.data = data 

        self.next = None

  '''

class Solution:

    def sortedInsert(self, head, data):

        #code here

Solutions:
class Solution:

	def sortedInsert(self, head, data):
		ptr = head
		lst = []
		visited = set()
		while ptr:
			if ptr in visited:
				break
			visited.add(ptr)
			lst.append(ptr.data)
			ptr = ptr.next
		i = 0
		x = []
		flag = False
		while i < len(lst):
			if lst[i] >= data and flag == False:
				x.append(data)
				flag = True
			x.append(lst[i])
			i += 1
		ll = LinkedList()
		for i in x:
			ll.push(i)
		return ll.head


class Solution:

	def sortedInsert(self, head, data):
		if data <= head.data:
			cur_val = head.data
			head.data = data
			temp = Node(cur_val)
			temp.next = head.next
			head.next = temp
			return head
		temp = head
		while temp.next != head:
			if data >= temp.data and data <= temp.next.data:
				node = Node(data)
				node.next = temp.next
				temp.next = node
				return head
			temp = temp.next
		node = Node(data)
		node.next = head
		temp.next = node
		return head


class Solution:

	def sortedInsert(self, head, data):
		(temp, new_Node, flag) = (head, Node(data), False)
		if head.data >= new_Node.data:
			flag = True
		while temp.next:
			if temp.next == head:
				temp.next = new_Node
				new_Node.next = head
				if flag:
					head = new_Node
				break
			if temp.next.data < data or flag:
				temp = temp.next
			else:
				k = temp.next
				new_Node.next = k
				temp.next = new_Node
				break
		return head


class Node:

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

class Solution:

	def sortedInsert(self, head, data):
		new_node = Node(data)
		if head is None:
			new_node.next = new_node
			return new_node
		if data < head.data:
			curr = head
			while curr.next != head:
				curr = curr.next
			curr.next = new_node
			new_node.next = head
			return new_node
		curr = head
		while curr.next != head and curr.next.data < data:
			curr = curr.next
		new_node.next = curr.next
		curr.next = new_node
		return head


class Solution:

	def sortedInsert(self, head, data):
		l = head
		if head.data > data:
			t = Node(data)
			t.next = head
			while l.next != head:
				l = l.next
			l.next = t
			return t
		prev = None
		cur = head
		h = head
		h1 = head
		while cur.next != head:
			if cur.data >= data:
				prev.next = Node(data)
				prev = prev.next
				prev.next = cur
				return h
			else:
				prev = cur
				cur = cur.next
		while h1.next != head:
			h1 = h1.next
		h1.next = Node(data)
		h1 = h1.next
		h1.next = head
		return h


class Solution:

	def sortedInsert(self, head, data):
		new_node = Node(data)
		n = head
		if n.data >= data:
			while n.next != head:
				n = n.next
			new_node.next = head
			n.next = new_node
			head = new_node
			return head
		else:
			while n.next != head:
				if n.next.data >= data:
					new_node.next = n.next
					n.next = new_node
					break
				n = n.next
		if n.next == head:
			n.next = new_node
			new_node.next = head
		return head


class Solution:

	def sortedInsert(self, head, data):
		next_node = head
		prev_node = head
		new_node = Node(data)
		if head is None:
			new_node.next = new_node
			head = new_node
		if head.data >= data:
			while next_node.next != head:
				next_node = next_node.next
			next_node.next = new_node
			new_node.next = head
			head = new_node
			return head
		while next_node.next != head:
			if next_node.data >= data:
				prev_node.next = new_node
				new_node.next = next_node
				return head
			prev_node = next_node
			next_node = next_node.next
		if next_node.next == head:
			next_node.next = new_node
			new_node.next = head
			return head


class Solution:

	def sortedInsert(self, head, data):
		if head is None:
			return head
		if head.next == head:
			if head.data < data:
				node = Node(data)
				head.next = node
				node.next = head
				return head
			else:
				node = Node(data)
				node.next = head
				head.next = node
				return node
		if data < head.data:
			tmp = head
			node = Node(data)
			node.next = head
			while tmp.next != head:
				tmp = tmp.next
			tmp.next = node
			return node
		prev = head
		curr = head
		while curr.data < data and curr.next != head:
			prev = curr
			curr = curr.next
		if curr.next != head:
			node = Node(data)
			prev.next = node
			node.next = curr
		elif curr.data < data:
			node = Node(data)
			curr.next = node
			node.next = head
		else:
			node = Node(data)
			prev.next = node
			node.next = curr
		return head


class Solution:

	def sortedInsert(self, head, data):
		if head.data > data:
			p = head
			while head.next != p:
				head = head.next
			p = head.next
			head.next = Node(data)
			head.next.next = p
			return head.next
		h = head
		while head.next.data <= data:
			head = head.next
		p = head.next
		head.next = Node(data)
		head.next.next = p
		return h


class Solution:

	def sortedInsert(self, head, data):
		newnode = Node(data)
		newnode.next = newnode
		if head == None:
			return newnode
		if data <= head.data:
			newnode.next = head
			curr = head
			while curr.next != head:
				curr = curr.next
			curr.next = newnode
			return newnode
		else:
			curr = head
			while curr.next != head:
				if data <= curr.next.data:
					temp = curr.next
					curr.next = newnode
					newnode.next = temp
					break
				curr = curr.next
			if curr.next == head:
				curr.next = newnode
			return head


class Solution:

	def sortedInsert(self, head, data):
		new_data = Node(data)
		curr = head
		if head.data > data:
			new_data.next = head.next
			head.next = new_data
			(new_data.data, head.data) = (head.data, new_data.data)
			return head
		while curr.next:
			if curr.next.data >= data or curr.next.data is head:
				new_data.next = curr.next
				curr.next = new_data
				break
			curr = curr.next
		return head


class Solution:

	def sortedInsert(self, head, data):
		new_node = Node(data)
		if head is None:
			new_node.next = new_node
			return new_node
		if data < head.data:
			current = head
			while current.next != head:
				current = current.next
			current.next = new_node
			new_node.next = head
			return new_node
		current = head
		while current.next != head and current.next.data < data:
			current = current.next
		new_node.next = current.next
		current.next = new_node
		return head


class Solution:

	def sortedInsert(self, head, data):
		tmp = head
		new_node = Node(data)
		if not head:
			head = new_node
			new_node.next = head
			return head
		while 1:
			if data >= tmp.data and data <= tmp.next.data:
				new_node.next = tmp.next
				tmp.next = new_node
				break
			if tmp.next == head and data >= tmp.data:
				new_node.next = tmp.next
				tmp.next = new_node
				break
			if tmp.next == head and data <= tmp.data:
				new_node.next = head
				head = new_node
				tmp.next = new_node
				break
			tmp = tmp.next
		return head


class Solution:

	def sortedInsert(self, head, data):
		if head is None:
			return None
		temp = head
		new_node = Node(data)
		if temp.next == temp:
			temp.next = new_node
			new_node.next = temp
			if data < temp.data:
				return new_node
			else:
				return temp
		if data < head.data:
			while temp.next != head:
				temp = temp.next
			new_node.next = temp.next
			temp.next = new_node
			return new_node
		else:
			while temp.next != head:
				if data < temp.next.data:
					new_node.next = temp.next
					temp.next = new_node
					return head
				else:
					temp = temp.next


class Solution:

	def sortedInsert(self, head, key):
		tmp = head
		temp = Node(key)
		if head.data > key:
			temp.next = head.next
			head.next = temp
			(head.data, temp.data) = (temp.data, head.data)
			return tmp
		while head.next and head.next.data < key:
			if head.next == tmp:
				break
			head = head.next
		temp.next = head.next
		head.next = temp
		return tmp