Given a sorted doubly linked list and an element X, your need to insert the element X into correct position in the sorted DLL.
Example:
Input:
LinkedList:
X = 9
Output:
Your Task:
You only need to complete the function sortedInsert() that takes head reference and x as arguments and returns the head of the modified list. The printing and checking tasks are done by the driver code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
1 <= Number of nodes <= 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

        self.prev = None

'''



def sortedInsert(head, x):

    #code here

Solutions:
def sortedInsert(head, x):
	n = Node(x)
	if head is None:
		head = n
	elif head.data >= n.data:
		n.next = head
		n.next.prev = n
		head = n
	else:
		current = head
		while current.next is not None and current.next.data < n.data:
			current = current.next
		n.next = current.next
		if current.next is not None:
			n.next.prev = n
		current.next = n
		n.prev = current
	return head


def sortedInsert(head, x):
	temp = Node(x)
	cur = head
	if head == None:
		return temp
	elif x < head.data:
		temp.next = head
		head.prev = temp
		return temp
	while cur.next != None and cur.next.data < x:
		cur = cur.next
	if cur.next == None:
		temp.next = cur.next
		cur.next = temp
		temp.prev = cur
	else:
		temp.next = cur.next
		cur.next.prev = temp
		cur.next = temp
		temp.prev = cur
	return head


def sortedInsert(head, x):
	h = head
	node = Node(x)
	if not head:
		return node
	elif head.data >= x:
		node.next = head
		node.next.prev = node
		return node
	curr = head
	while curr.next and curr.next.data < x:
		curr = curr.next
	node.next = curr.next
	if curr.next:
		node.next.prev = node
	curr.next = node
	node.prev = curr
	return head


def sortedInsert(head, x):
	curr = head
	while curr.next and curr.next.data < x:
		curr = curr.next
	if curr == head and x < curr.data:
		n_node = Node(x)
		n_node.next = head
		head.prev = n_node
		head = n_node
	else:
		n_node = Node(x)
		n_node.prev = curr
		n_node.next = curr.next
		curr.next = n_node
		if n_node.next != None:
			n_node.next.prev = n_node
	return head


def sortedInsert(head, x):
	new = Node(x)
	if head is None:
		return new
	if x < head.data:
		new.next = head
		head.prev = new
		return new
	curr = head
	while curr.next is not None:
		nxt = curr.next
		if x >= curr.data and x < nxt.data:
			curr.next = new
			new.prev = curr
			new.next = nxt
			nxt.prev = new
			return head
		curr = curr.next
	curr.next = new
	new.prev = curr
	return head


def sortedInsert(head, x):
	a = head
	p = []
	while a is not None:
		p.append(a.data)
		a = a.next
	p.append(x)
	q = sorted(p)
	head1 = None
	newnode = None
	for i in q:
		m = Node(i)
		if head1 is None:
			head1 = m
			newnode = head1
		else:
			newnode.next = m
			m.prev = newnode
			newnode = newnode.next
	return head1


def sortedInsert(head, x):
	temp = Node(x)
	if head == None:
		return None
	if temp.data < head.data:
		temp.next = head
		head.prev = temp
		return temp
	curr = head
	node = Node(x)
	while curr.next and curr.next.data < x:
		curr = curr.next
	node.next = curr.next
	if curr.next:
		node.next.prev = node
	curr.next = node
	node.prev = curr
	return head


def sortedInsert(head, x):
	new_node = Node(x)
	temp = head
	if temp.next is None:
		if temp.data > x:
			new_node.next = temp
			temp.prev = new_node
			head = new_node
		else:
			temp.next = new_node
			new_node.prev = temp
	elif temp.data > x:
		new_node.next = temp
		temp.prev = new_node
		head = new_node
	else:
		while temp.next != None:
			if temp.data > x:
				break
			temp = temp.next
		if temp.next != None:
			new_node.prev = temp.prev
			new_node.next = temp
			temp.prev.next = new_node
			temp.prev = new_node
		elif temp.data <= x:
			temp.next = new_node
			new_node.prev = temp
		else:
			new_node.prev = temp.prev
			new_node.next = temp
			temp.prev.next = new_node
			temp.prev = new_node
	return head


def sortedInsert(head, x):
	n = head
	N = Node(x)
	if n.data >= x:
		N.next = head
		head.prev = N
		head = N
	else:
		while n.next != None:
			if n.data >= x:
				n.prev.next = N
				N.prev = n.Prev
				N.next = n
				n.prev = N
				break
			n = n.next
			if n.data >= x:
				n.prev.next = N
				N.prev = n.prev
				N.next = n
				n.prev = N
				break
		else:
			N.prev = n
			n.next = N
	return head


def sortedInsert(head, x):
	new_node = Node(x)
	if head.data >= x:
		new_node.next = head
		head.prev = new_node
		head = new_node
	else:
		n = head
		while n.next is not None:
			if n.next.data >= x:
				break
			n = n.next
		if n.next is None:
			n.next = new_node
			new_node.prev = n
		else:
			new_node.next = n.next
			n.next.prev = new_node
			new_node.prev = n
			n.next = new_node
	return head


def sortedInsert(head, x):
	curr = head
	while curr and curr.next and (curr.data < x):
		curr = curr.next
	if curr.data >= x:
		new_node = Node(curr.data)
		curr.data = x
		new_node.next = curr.next
		if new_node.next:
			new_node.next.prev = new_node
	else:
		new_node = Node(x)
	new_node.prev = curr
	curr.next = new_node
	return head


def sortedInsert(head, x):
	n = Node(x)
	if head == None:
		return n
	curr = head
	if curr.data > x:
		n.next = curr
		curr.prev = n
		return n
	while curr.next != None:
		if curr.next.data > x:
			break
		curr = curr.next
	n.next = curr.next
	if curr.next != None:
		curr.next.prev = n
	curr.next = n
	n.prev = curr
	return head


def sortedInsert(head, x):
	new = Node(x)
	if head == None:
		return new
	elif head.data >= new.data:
		new.next = head
		new.next.prev = new
		head = new
	else:
		curr = head
		while curr.next != None and curr.next.data < new.data:
			curr = curr.next
		new.next = curr.next
		if curr.next != None:
			curr.next.prev = new
		curr.next = new
		new.prev = curr
	return head


def sortedInsert(head, x):
	temp = Node(x)
	if head is None:
		return temp
	curr = head
	while curr and curr.next:
		if curr.data <= x and curr.next.data > x:
			temp.next = curr.next
			temp.prev = curr
			curr.next.prev = temp
			curr.next = temp
			return head
		elif x <= curr.data:
			temp.next = curr
			curr.prev = temp
			return temp
		curr = curr.next
	curr.next = temp
	temp.prev = curr
	return head


def sortedInsert(head, x):
	s = Node(x)
	if x <= head.data:
		s.next = head
		head.prev = s
		head = s
		return head
	itr = head
	prev = None
	while itr:
		prev = itr
		itr = itr.next
	if prev.data < x:
		prev.next = s
		s.prev = prev
		return head
	itr = head
	prev = None
	while itr.data <= x:
		prev = itr
		itr = itr.next
	prev.next = s
	itr.prev = s
	s.prev = prev
	s.next = itr
	return head


def sortedInsert(head, x):
	temp = Node(x)
	curr = head
	c = 1
	while curr.next is not None and curr.data < temp.data:
		curr = curr.next
		c += 1
	if c == 1:
		temp.next = head
		head.prev = temp
		return temp
	if curr.next is None:
		if curr.data < temp.data:
			curr.next = temp
			temp.prev = curr
			return head
	temp.next = curr
	temp.prev = curr.prev
	curr.prev.next = temp
	curr.prev = temp
	return head


def sortedInsert(head, x):
	temp = Node(x)
	curr = head
	prev = head
	if head.data >= x:
		head.prev = temp
		temp.next = head
		head = temp
		return head
	while curr.next:
		if curr.data < x <= curr.next.data:
			temp.prev = curr
			temp.next = curr.next
			curr.next.prev = temp
			curr.next = temp
			return head
		else:
			prev = curr
			curr = curr.next
	temp.prev = curr
	curr.next = temp
	return head


class Node:

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

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


def sortedInsert(head, x):
	temp = Node(x)
	if head is None:
		return head
	if head.data >= x:
		temp.next = head
		head.prev = temp
		return temp
	curr = head
	while curr.next is not None:
		if curr.data > x:
			temp.prev = curr.prev
			curr.prev.next = temp
			temp.next = curr
			curr.prev = temp
			return head
		curr = curr.next
	if curr.data > x:
		temp.prev = curr.prev
		curr.prev.next = temp
		temp.next = curr
		curr.prev = temp
	else:
		curr.next = temp
		temp.prev = curr
	return head


def sortedInsert(head, x):
	ptr = head
	lst = []
	while ptr:
		lst.append(ptr.data)
		ptr = ptr.next
	y = []
	i = 0
	flag = False
	while i < len(lst):
		if lst[i] >= x and flag == False:
			y.append(x)
			flag = True
		y.append(lst[i])
		i += 1
	if flag == False:
		y.append(x)
	ll = doublyLL()
	tail = None
	for i in y:
		tail = ll.insert(tail, i)
	return ll.head


def sortedInsert(head, x):
	new = Node(x)
	if x < head.data:
		new.next = head
		head.prev = new
		return new
	curr = head
	while curr and curr.next and (curr.next.data < x):
		curr = curr.next
	new.next = curr.next
	new.prev = curr
	if curr.next:
		curr.next.prev = new
	curr.next = new
	return head


def sortedInsert(head, x):
	newNode = Node(x)
	curr = head
	while curr.next and curr.next.data < x:
		curr = curr.next
	if curr == head and curr.data >= x:
		newNode.next = curr
		curr.prev = newNode
		return newNode
	if curr == head:
		newNode.next = curr.next
		curr.next.prev = newNode
		curr.next = newNode
		newNode.prev = curr
		return head
	elif curr.next == None:
		curr.next = newNode
		newNode.prev = curr
		return head
	curr.next.prev = newNode
	newNode.next = curr.next
	curr.next = newNode
	newNode.prev = curr
	return head


def sortedInsert(head, x):
	node = Node(x)
	if head == None:
		return node
	if x < head.data or x == head.data:
		node.next = head
		head.prev = node
		head = node
		return head
	curr = head
	prev = head
	while curr:
		if x <= curr.data:
			node.next = curr
			curr.prev.next = node
			node.prev = curr.prev
			curr.prev = node
			return head
		else:
			prev = curr
			curr = curr.next
	prev.next = node
	node.prev = prev
	return head


def sortedInsert(head, x):
	temp = head
	newnode = Node(x)
	if temp.data >= x:
		newnode.next = temp
		temp.prev = newnode
		head = newnode
		return head
	while temp.next.next:
		if temp.next.data >= x:
			break
		temp = temp.next
	leftval = temp.next
	if leftval.data >= x:
		temp.next = newnode
		newnode.prev = temp
		newnode.next = leftval
		leftval.prev = newnode
	else:
		leftval.next = newnode
		newnode.prev = leftval
	return head


def sortedInsert(head, x):
	node = Node(x)
	if head.data >= x:
		head.prev = node
		node.next = head
		return node
	curr = head
	right = curr.next
	while curr != None:
		if right == None:
			curr.next = node
			node.prev = curr
			break
		if curr.data <= x and right.data > x:
			node.next = right
			node.prev = curr
			curr.next = node
			right.prev = node
			break
		curr = right
		right = curr.next
	return head


def sortedInsert(head, x):
	n = Node(x)
	if head.data > n.data:
		n.next = head
		head.prev = n
		head = n
	else:
		tmp = head
		flg = 0
		while tmp:
			if tmp.data > n.data:
				n.next = tmp
				n.prev = tmp.prev
				n.prev.next = n
				tmp.prev = n
				flg = 1
				break
			tmp = tmp.next
		if flg == 0:
			tmp = head
			while tmp.next:
				tmp = tmp.next
			tmp.next = n
			n.prev = tmp
	return head


def sortedInsert(head, x):
	new_node = Node(x)
	curr = head
	if head.data >= x:
		new_node.next = head
		new_node.prev = None
		head.prev = new_node
		return new_node
	while curr.next != None:
		if curr.next.data >= x:
			temp = curr.next
			curr.next = new_node
			new_node.next = temp
			new_node.prev = curr
			temp.prev = new_node
			return head
		curr = curr.next
	if curr.data < x:
		new_node.next = None
		new_node.prev = curr
		curr.next = new_node
		return head


def sortedInsert(head, x):
	temp = Node(x)
	c1 = head
	if head == None:
		return temp
	if head.data > temp.data:
		temp.next = head
		head.prev = temp
		return temp
	if head.next == None:
		head.next = temp
		temp.prev = head
		return head
	while c1.next.data < temp.data:
		c1 = c1.next
		if c1.next == None:
			break
	if c1.next == None:
		c1.next = temp
		temp.prev = c1
		return head
	else:
		temp.next = c1.next
		c1.next.prev = temp
		temp.prev = c1
		c1.next = temp
		return head


def sortedInsert(head, x):
	(cur, tmp) = (head, Node(x))
	if cur.data > tmp.data:
		(cur.prev, tmp.next) = (tmp, cur)
		return tmp
	while cur.next:
		if cur.data <= tmp.data <= cur.next.data:
			break
		cur = cur.next
	(tmp.prev, tmp.next) = (cur, cur.next)
	cur.next = tmp
	if tmp.next != None:
		tmp.next.prev = tmp
	return head


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


def sortedInsert(head, x):
	newnode = Node(x)
	if head.data > x:
		head.prev = newnode
		newnode.next = head
		head = newnode
		return head
	prev = head
	temp = head.next
	while temp != None:
		if temp.data > x:
			tempp = temp.prev
			newnode.prev = temp.prev
			newnode.next = temp
			temp.prev = newnode
			tempp.next = newnode
			return head
		prev = temp
		temp = temp.next
	prev.next = newnode
	newnode.prev = prev
	return head


def sortedInsert(head, x):
	temp = head
	new = Node(x)
	if temp.data >= x:
		temp.prev = new
		new.next = temp
		head = new
		return head
	while temp.next != None:
		if temp.data <= x and temp.next.data >= x:
			a = temp.next
			new.prev = temp
			new.next = a
			temp.next = new
			new.next.prev = new
			return head
		temp = temp.next
	if temp.data < x:
		temp.next = new
		new.prev = temp
		return head


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


def sortedInsert(head, x):
	if head.data >= x:
		node = Node(x)
		head.prev = node
		node.next = head
		return node
	stack = [head]
	while len(stack) > 0:
		current = stack.pop()
		if current.next:
			if current.next.data >= x:
				node = Node(x)
				node.next = current.next
				node.prev = current
				current.next.prev = node
				current.next = node
				return head
			stack.append(current.next)
		else:
			node = Node(x)
			current.next = node
			node.prev = current
			return head


def sortedInsert(head, x):
	elem = Node(x)
	if head == None:
		head = elem
	if head.next == None:
		if head.data > elem.data:
			elem.next = head
			head.prev = elem
			head = elem
		else:
			head.next = elem
			elem.prev = head
		return head
	curr = head
	flag = 'asc'
	if curr.data > curr.next.data:
		flag = 'desc'
	if flag == 'asc':
		while curr.next != None and curr.next.data < elem.data:
			curr = curr.next
	else:
		while curr.next != None and curr.next.data > elem.data:
			curr = curr.next
	if curr == head and curr.data > elem.data and (flag == 'asc'):
		elem.next = head
		head.prev = elem
		head = elem
	elif curr == head and curr.data < elem.data and (flag == 'desc'):
		elem.next = head
		head.prev = elem
		head = elem
	else:
		elem.next = curr.next
		if curr.next != None:
			curr.next.prev = elem
		elem.prev = curr
		curr.next = elem
	return head


def sortedInsert(head, x):
	if head.data > x:
		node = Node(x)
		head.prev = node
		node.next = head
		head = node
		return head
	curr = head
	while curr:
		if curr.data > x:
			prev = curr.prev
			node = Node(x)
			prev.next = node
			node.prev = prev
			node.next = curr
			curr.prev = node
			return head
		if curr.next:
			curr = curr.next
		else:
			break
	node = Node(x)
	node.prev = curr
	curr.next = node
	return head


def sortedInsert(head, x):
	a = Node(x)
	p = head
	while p != None:
		if head.data >= x:
			a.next = head
			head.prev = a
			head = a
			return head
		elif p.data <= x and p.next.data >= x:
			a.prev = p
			p.next.prev = a
			a.next = p.next
			p.next = a
			p = p.next
			return head
		else:
			p = p.next
			if p.next == None:
				p.next = a
				a.prev = p
				return head


def sortedInsert(head, x):
	newNode = Node(x)
	temp = head
	if head is None:
		return newNode
	elif x < head.data:
		newNode.prev = None
		newNode.next = head
		head.prev = newNode
		head = newNode
		return newNode
	while temp.next != None and x > temp.next.data:
		temp = temp.next
	if temp.next == None:
		newNode.next = temp.next
		newNode.prev = temp
		temp.next = newNode
	else:
		newNode.next = temp.next
		newNode.prev = temp
		newNode.next.prev = newNode
		temp.next = newNode
	return head


def sortedInsert(head, x):
	temp = Node(x)
	if head.data > x:
		temp.next = head
		head.prev = temp
		return temp
	curr = head
	while curr.next != None and curr.next.data < x:
		curr = curr.next
	if curr.next != None:
		n = curr.next
		n.prev = temp
		temp.next = n
		curr.next = temp
		temp.prev = curr
	else:
		temp.next = curr.next
		curr.next = temp
		temp.prev = curr
	return head


def sortedInsert(head, x):
	curr = head
	new_node = Node(x)
	inserted = False
	while curr:
		if curr == head:
			if x < curr.data:
				new_node.next = head
				head.prev = new_node
				head = new_node
				return head
		elif x < curr.data:
			new_node.next = curr
			new_node.prev = curr.prev
			curr.prev.next = new_node
			curr.prev = new_node
			return head
		if curr.next == None:
			curr.next = new_node
			new_node.prev = curr
			return head
		curr = curr.next


def sortedInsert(head, x):
	head_c = head
	if x < head.data:
		temp_node = Node(x)
		temp_node.next = head
		head.prev = temp_node
		return temp_node
	while head.next != None:
		if head.next.data >= x:
			break
		head = head.next
	tmp_node = Node(x)
	if head.next == None:
		head.next = tmp_node
		tmp_node.prev = head
		return head_c
	tmp_node.next = head.next
	tmp_node.prev = head
	head.next.prev = tmp_node
	head.next = tmp_node
	return head_c


def sortedInsert(head, x):
	curr = head
	q = Node(x)
	if head.data > x:
		q.next = head
		head.prev = q
		return q
	while curr.next != None:
		curr = curr.next
	if curr.data <= x:
		curr.next = q
		q.prev = curr
		return head
	curr = head
	fast = head
	while curr.data <= x:
		fast = curr
		curr = curr.next
	q.next = curr
	curr.prev = q
	q.prev = fast
	fast.next = q
	return head


class Node:

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

def sortedInsert(head, x):
	newNode = Node(x)
	if not head:
		head = newNode
	elif x <= head.data:
		newNode.next = head
		head.prev = newNode
		head = newNode
	else:
		node = head
		while node.next and node.next.data < x:
			node = node.next
		newNode.next = node.next
		if node.next:
			node.next.prev = newNode
		node.next = newNode
		newNode.prev = node
	return head


def sortedInsert(head, x):
	temp = Node(x)
	curr = head
	if curr == None:
		return head
	if curr.next == None:
		if x < curr.data:
			temp.next = head
			temp.prev = None
			return temp
		else:
			head.next = temp
			temp.prev = head
			return head
	if x < head.data:
		curr.prev = temp
		temp.next = curr
		return temp
	while curr != None and curr.next.data < x:
		curr = curr.next
		if curr.next == None:
			break
	if curr.next != None:
		temp.next = curr.next
		curr.next.prev = temp
		temp.prev = curr
		curr.next = temp
		return head
	elif curr.next == None:
		temp.next = None
		curr.next = temp
		temp.prev = curr
		return head


def sortedInsert(head, x):
	newNode = Node(x)
	if not head:
		head = newNode
		return head
	elif head.data > x:
		newNode.next = head
		newNode.next.prev = newNode
		head = newNode
		return head
	else:
		currNode = head
		while currNode.next and currNode.next.data < x:
			currNode = currNode.next
		newNode.next = currNode.next
		if currNode.next:
			currNode.next.prev = newNode
		currNode.next = newNode
		newNode.prev = currNode
		return head


def sortedInsert(head, x):
	t = head
	k = Node(x)
	k.next = None
	k.prev = None
	if x <= t.data:
		k.next = t
		t.prev = k
		head = k
		return head
	while t.next != None:
		h = t.next
		if x >= t.data and x <= t.next.data:
			t.next = k
			k.prev = t
			k.next = h
			h.prev = k
			return head
		t = t.next
	t.next = k
	k.prev = t
	return head


def sortedInsert(head, x):
	new_node = Node(x)
	temp_node = head
	if x <= head.data:
		new_node.next = head
		head = new_node
		temp_node.prev = new_node
	else:
		last_node = head
		while last_node.next is not None:
			last_node = last_node.next
		if x >= last_node.data:
			last_node.next = new_node
			new_node.prev = last_node
		else:
			while temp_node.next.data < x:
				temp_node = temp_node.next
			next_node = temp_node.next
			temp_node.next = new_node
			new_node.next = next_node
			next_node.prev = new_node
			new_node.prev = temp_node
	return head


def sortedInsert(head, x):
	copyHead = head
	while head and head.data < x:
		if not head.next:
			end = head
		head = head.next
	if not head:
		newEnd = Node(x)
		end.next = newEnd
		newEnd.prev = end
	elif head.data >= x:
		newNode = Node(x)
		temp = head.prev
		head.prev = newNode
		newNode.next = head
		if temp:
			newNode.prev = temp
			temp.next = newNode
		else:
			return newNode
	return copyHead


def sortedInsert(head, x):
	if head.data > x:
		start = Node(x)
		start.next = head
		head.prev = start
		return start
	start = head
	while head.next and head.next.data < x:
		head = head.next
	temp = head.next
	head.next = Node(x)
	head.next.next = temp
	head.next.prev = head
	if temp:
		temp.prev = head.next
	return start


def sortedInsert(head, x):
	temp = head
	node = Node(x)
	if head is None:
		return head
	if head.data >= x:
		temp.prev = node
		node.next = temp
		head = node
		return head
	while temp.next is not None:
		if temp.next.data > x:
			temp.next.prev = node
			node.next = temp.next
			node.prev = temp
			temp.next = node
			return head
		temp = temp.next
	temp.next = node
	node.prev = temp
	return head


def sortedInsert(head, x):
	temp = head
	N = Node(x)
	if head.data >= x:
		N.next = head
		head.prev = N
		head = N
		return head
	while temp.next:
		if temp.data <= x and temp.next.data >= x:
			t = temp.next
			N.next = temp.next
			N.prev = temp
			temp.next = N
			t.prev = N
			return head
		temp = temp.next
	temp.next = N
	N.prev = temp
	return head


def sortedInsert(head, x):
	node = Node(x)
	if x < head.data:
		(node.next, head.prev) = (head, node)
		return node
	cur = head
	while cur.next and cur.next.data < x:
		cur = cur.next
	if cur.next is None:
		(cur.next, node.prev) = (node, cur)
	else:
		nxt = cur.next
		cur.next = node
		node.prev = cur
		node.next = nxt
		nxt.prev = node
	return head


def sortedInsert(head, x):
	c = 0
	curr = head
	temp = Node(x)
	if temp.data < head.data:
		temp.next = head
		head.prev = temp
		temp.prev = None
		head = temp
		return head
	elif n == 1:
		head.next = temp
		temp.prev = head
		temp.next = None
		return head
	else:
		while curr.next is not None:
			if curr.data <= x and curr.next.data > x:
				a = curr.next
				curr.next = temp
				temp.prev = curr
				temp.next = a
				a.prev = temp
				break
			curr = curr.next
		if curr.data < x and curr.next == None:
			curr.next = temp
			temp.prev = curr
			temp.next = None
		return head