Given a linked list sorted in ascending order and an integer called data, insert data in the linked list such that the list remains sorted.
Example 1:
Input:
LinkedList: 25->36->47->58->69->80
data: 19
Output: 19 25 36 47 58 69 80
Example 2:
Input:
LinkedList: 50->100
data: 75
Output: 50 75 100
Your Task:
The task is to complete the function sortedInsert() which should insert the element in sorted Linked List and return the head of the linked list
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{4}
-99999 <= A[i] <= 99999, for each valid i

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 Solution:

    def sortedInsert(self, head1,key):

        # code here

        # return head of edited linked list



Solutions:
class Solution:

	def sortedInsert(self, head1, key):
		newNode = Node(key)
		if head1 == None:
			return newNode
		if head1.data > key:
			newNode.next = head1
			head1 = newNode
			return head1
		current = head1
		while current.next:
			if current.next.data > key:
				newNode.next = current.next
				current.next = newNode
				return head1
			current = current.next
		current.next = newNode
		return head1


class Solution:

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


class Solution:

	def sortedInsert(self, head1, key):
		temp = Node(key)
		if head1.data > key:
			temp.next = head1
			return temp
		curr = head1
		if curr is None:
			return temp
		while curr.next is not None and curr.next.data < key:
			curr = curr.next
		temp.next = curr.next
		curr.next = temp
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		temp = Node(key)
		if head1 == None:
			head1 = temp
			return head1
		elif head1.data >= temp.data:
			temp.next = head1
			head1 = temp
			return head1
		else:
			pointer = head1
			while pointer.next != None and temp.data > pointer.next.data:
				pointer = pointer.next
			temp.next = pointer.next
			pointer.next = temp
			return head1


class Solution:

	def sortedInsert(self, head1, key):
		n = head1
		if key <= head1.data:
			m = Node(key)
			m.next = n
			head1 = m
			return head1
		while n.next != None:
			if n.data <= key <= n.next.data:
				m = Node(key)
				m.next = n.next
				n.next = m
				return head1
			n = n.next
		m = Node(key)
		n.next = m
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		h = head1
		k = head1
		if key < head1.data:
			t = Node(key)
			t.next = head1
			return t
		prev = head1
		h1 = head1
		h1 = h1.next
		while h1:
			if key < h1.data:
				n = h1
				prev.next = Node(key)
				prev = prev.next
				prev.next = n
				return head1
			else:
				prev = h1
				h1 = h1.next
		while k.next:
			k = k.next
		k.next = Node(key)
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		item = head1
		previtem = None
		yeniitem = Node(key)
		while item != None:
			if key < item.data:
				if previtem == None:
					yeniitem.next = item
					return yeniitem
				else:
					previtem.next = yeniitem
					yeniitem.next = item
					return head1
			previtem = item
			item = item.next
		previtem.next = yeniitem
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		new_node = Node(key)
		next_node = head1
		prev_node = None
		if key <= head1.data:
			new_node.next = head1
			head1 = new_node
			return head1
		while next_node:
			if key <= next_node.data:
				prev_node.next = new_node
				new_node.next = next_node
				return head1
			else:
				prev_node = next_node
				next_node = next_node.next
		if next_node is None:
			prev_node.next = new_node
			new_node.next = None
			return head1


class Solution:

	def sortedInsert(self, head, key):
		a = []
		cur = head
		while cur:
			a.append(cur.data)
			cur = cur.next
		a.append(key)
		a.sort()
		n = Node(0)
		h = n
		for i in a:
			new = Node(i)
			n.next = new
			n = n.next
		return h.next


class Solution:

	def sortedInsert(self, head1, key):
		new_node = Node(key)
		if head1.data >= key:
			new_node.next = head1
			head1 = new_node
		else:
			n = head1
			while n.next is not None:
				if n.next.data > key:
					break
				n = n.next
			if n.next is None:
				n.next = new_node
			else:
				new_node.next = n.next
				n.next = new_node
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		dummy = Node(key)
		if head1.data > key:
			dummy.next = head1
			head1 = dummy
			return head1
		curr = head1
		while curr.next != None:
			if curr.data <= key and curr.next.data >= key:
				temp = curr.next
				curr.next = dummy
				dummy.next = temp
				return head1
			else:
				curr = curr.next
		curr.next = dummy
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		prev = Node(0)
		prev.next = head1
		curr = prev
		newNode = Node(key)
		if not head1:
			return newNode
		while curr.next and curr.next.data < key:
			curr = curr.next
		temp = curr.next
		curr.next = newNode
		newNode.next = temp
		return prev.next


class Solution:

	def sortedInsert(self, head1, key):
		temp = Node(key)
		if head1 is None:
			temp.next = head1
			head1 = temp
		elif temp.data <= head1.data:
			temp.next = head1
			head1 = temp
		else:
			cur = head1
			while cur.next is not None and temp.data > cur.next.data:
				cur = cur.next
			temp.next = cur.next
			cur.next = temp
		return head1


class Solution:

	def sortedInsert(self, head, key):
		temp = Node(key)
		if head.data > temp.data:
			temp.next = head
			return temp
		curr = head
		while curr.next is not None:
			if curr.next.data >= temp.data:
				temp.next = curr.next
				curr.next = temp
				break
			curr = curr.next
		if curr.data < temp.data:
			curr.next = temp
		return head


class Node:

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

class Solution:

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


class Solution:

	def sortedInsert(self, head1, key):
		a = head1
		p = []
		while a is not None:
			p.append(a.data)
			a = a.next
		p.append(key)
		q = sorted(p)
		head2 = None
		b = None
		for i in q:
			m = Node(i)
			if head2 is None:
				head2 = m
				b = head2
			else:
				b.next = m
				b = b.next
		return head2


class Solution:

	def sortedInsert(self, head1, key):
		cur = head1
		if head1.data > key:
			head1.prev = Node(key)
			head1.prev.next = head1
			return head1.prev
		while cur.next != None:
			if cur.data <= key:
				if cur.next.data > key:
					nxt = cur.next
					pv = cur
					pv.next = Node(key)
					pv.next.next = nxt
					return head1
			cur = cur.next
		cur.next = Node(key)
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		new = Node(key)
		curr = head1
		prev = curr
		if key < curr.data:
			new.next = head1
			return new
		while curr != None and curr.data <= key:
			prev = curr
			curr = curr.next
		prev.next = new
		new.next = curr
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		if key <= head1.data:
			newNode = Node(key)
			newNode.next = head1
			head1 = newNode
			return head1
		else:
			curr = head1
			while not (curr.next.data > key and curr.data <= key):
				curr = curr.next
				if curr.next is None:
					break
			if curr.next is None:
				newNode = Node(key)
				curr.next = newNode
				return head1
			else:
				newNode = Node(key)
				newNode.next = curr.next
				curr.next = newNode
				return head1


class Solution:

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


class Solution:

	def sortedInsert(self, head1, key):
		if head1 is None:
			new_node = Node(key)
			head1 = new_node
			return head1
		if key < head1.data:
			new_node = Node(key)
			new_node.next = head1
			head1 = new_node
			return head1
		curr = head1
		prev = None
		while curr:
			if key < curr.data:
				new_node = Node(key)
				new_node.next = curr
				prev.next = new_node
				return head1
			else:
				prev = curr
				curr = curr.next
		new_node = Node(key)
		prev.next = new_node
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		temp = head1
		prev_temp = None
		while temp:
			if temp.data < key:
				prev_temp = temp
				temp = temp.next
			else:
				node = Node(key)
				if prev_temp == None:
					node.next = head1
					head1 = node
					return head1
				node.next = prev_temp.next
				prev_temp.next = node
				return head1
		prev_temp.next = Node(key)
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		temp = head1
		flag = 0
		while temp.data < key:
			if temp.next:
				temp = temp.next
			else:
				flag = 1
				break
		if flag == 1:
			temp.next = Node(key)
			return head1
		dt = temp.data
		nxt = temp.next
		temp.data = key
		nn = Node(dt)
		nn.next = nxt
		temp.next = nn
		return head1


class Solution:

	def sortedInsert(self, head1, key):
		itr = head1
		l = []
		while itr:
			l.append(itr.data)
			itr = itr.next
		l.append(key)
		l.sort()
		head = Node(l[0])
		t = head
		for i in range(1, len(l)):
			x = Node(l[i])
			head.next = x
			head = head.next
		return t


class Solution:

	def sortedInsert(self, h, k):
		if h.data > k:
			n = Node(k)
			n.next = h
			h = n
			return h
		t = h
		while t.next:
			if t.data <= k <= t.next.data:
				n = Node(k)
				n.next = t.next
				t.next = n
				return h
			t = t.next
			if t.next == None:
				n = Node(k)
				t.next = n
				return h


class Solution:

	def sortedInsert(self, head, key):
		l = []
		h = head
		while h:
			l.append(h.data)
			h = h.next
		l.append(key)
		l.sort()
		a = b = Node(-1)
		for i in l:
			a.next = Node(i)
			a = a.next
		return b.next


class Solution:

	def sortedInsert(self, head, key):
		new_node = Node(key)
		if not head or key < head.data:
			new_node.next = head
			head = new_node
		else:
			curr_node = head
			next_node = head.next
			while next_node and next_node.data < key:
				curr_node = next_node
				next_node = next_node.next
			curr_node.next = new_node
			new_node.next = next_node
		return head


class Solution:

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