Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:
(i) a next pointer to the next node,
(ii) a bottom pointer to a linked list where this node is head.
Each of the sub-linked-list is in sorted order.
Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order. 
Note: The flattened list will be printed using the bottom pointer instead of the next pointer.
For more clarity have a look at the printList() function in the driver code.
 
Example 1:
Input:
5 -> 10 -> 19 -> 28
|     |     |     | 
7     20    22   35
|           |     | 
8          50    40
|                 | 
30               45
Output:  5-> 7-> 8- > 10 -> 19-> 20->
22-> 28-> 30-> 35-> 40-> 45-> 50.
Explanation:
The resultant linked lists has every 
node in a single level.
(Note: | represents the bottom pointer.)
 
Example 2:
Input:
5 -> 10 -> 19 -> 28
|          |                
7          22   
|          |                 
8          50 
|                           
30              
Output: 5->7->8->10->19->22->28->30->50
Explanation:
The resultant linked lists has every
node in a single level.
(Note: | represents the bottom pointer.)
 
Your Task:
You do not need to read input or print anything. Complete the function flatten() that takes the head of the linked list as input parameter and returns the head of flattened link list.
Expected Time Complexity: O(N*N*M)
Expected Auxiliary Space: O(1)
Constraints:
0 <= N <= 50
1 <= M_{i} <= 20
1 <= Element of linked list <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3





'''



class Node:

    def __init__(self, d):

        self.data=d

        self.next=None

        self.bottom=None

        

'''



def flatten(root):

    #Your code here

Solutions:
def merge(head1, head2):
	mergeHead = dummy = Node(None)
	(curr1, curr2) = (head1, head2)
	while curr1 and curr2:
		if curr1.data <= curr2.data:
			dummy.bottom = curr1
			curr1 = curr1.bottom
		else:
			dummy.bottom = curr2
			curr2 = curr2.bottom
		dummy = dummy.bottom
	if curr1:
		dummy.bottom = curr1
	if curr2:
		dummy.bottom = curr2
	return mergeHead.bottom

def flatten(root):
	head = root
	currRoot = root.next
	while currRoot:
		head = merge(head, currRoot)
		currRoot = currRoot.next
	return root


def flatten(root):
	if not root or not root.next:
		return root
	l2 = flatten(root.next)
	return merge(root, l2)

def merge(l1, l2):
	l1.next = None
	l2.next = None
	dummy = Node(0)
	cur = dummy
	while l1 and l2:
		if l1.data < l2.data:
			cur.bottom = l1
			l1 = l1.bottom
		else:
			cur.bottom = l2
			l2 = l2.bottom
		cur = cur.bottom
	cur.bottom = l1 if l1 else l2
	return dummy.bottom


def mergeLL(a, b):
	res = dummy = Node(0)
	while a and b:
		if a.data < b.data:
			dummy.bottom = a
			dummy = dummy.bottom
			a = a.bottom
		else:
			dummy.bottom = b
			dummy = dummy.bottom
			b = b.bottom
	if a:
		dummy.bottom = a
	if b:
		dummy.bottom = b
	return res.bottom

def flatten(root):
	if root is None or root.next is None:
		return root
	root.next = flatten(root.next)
	root = mergeLL(root, root.next)
	return root


def flatten(root):
	res_head = root
	front = head.next
	while front is not None:
		front1 = res_head
		front2 = front
		temp_head = None
		res = None
		while front1 is not None and front2 is not None:
			if front1.data > front2.data:
				if temp_head is None:
					temp_head = front2
					res = front2
				else:
					res.bottom = front2
					res = res.bottom
				front2 = front2.bottom
			else:
				if temp_head is None:
					temp_head = front1
					res = front1
				else:
					res.bottom = front1
					res = res.bottom
				front1 = front1.bottom
		if front1 is not None:
			res.bottom = front1
		if front2 is not None:
			res.bottom = front2
		res_head = temp_head
		front = front.next
	return res_head


def merge(lis1, lis2):
	res = Node(0)
	temp = res
	while lis1 and lis2:
		if lis1.data < lis2.data:
			temp.bottom = lis1
			temp = temp.bottom
			lis1 = lis1.bottom
		else:
			temp.bottom = lis2
			temp = temp.bottom
			lis2 = lis2.bottom
	if lis1 == None:
		temp.bottom = lis2
	else:
		temp.bottom = lis1
	return res.bottom

def flatten(root):
	if root is None or root.next is None:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def merge(node1, node2):
	temp = res = Node(0)
	while node1 and node2:
		if node1.data < node2.data:
			temp.bottom = node1
			temp = temp.bottom
			node1 = node1.bottom
		else:
			temp.bottom = node2
			temp = temp.bottom
			node2 = node2.bottom
	if node1:
		temp.bottom = node1
	elif node2:
		temp.bottom = node2
	return res.bottom

def flatten(root):
	if not root or not root.next:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def mergeLists(a, b):
	if not a:
		return b
	if not b:
		return a
	result = None
	if a.data <= b.data:
		result = a
		result.bottom = mergeLists(a.bottom, b)
	else:
		result = b
		result.bottom = mergeLists(a, b.bottom)
	return result

def flatten(head):
	if not head or not head.next:
		return head
	head.next = flatten(head.next)
	head = mergeLists(head, head.next)
	return head


def merge(a, b):
	res = Node(0)
	temp = res
	while a and b:
		if a.data < b.data:
			temp.bottom = Node(a.data)
			temp = temp.bottom
			a = a.bottom
		else:
			temp.bottom = Node(b.data)
			temp = temp.bottom
			b = b.bottom
	if a:
		temp.bottom = a
	if b:
		temp.bottom = b
	return res.bottom

def flatten(root):
	if root is None or root.next is None:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def flatten(root):
	l2 = root.next
	while l2:
		next_list = l2.next
		root = merge_list(root, l2)
		l2 = next_list
	return root

def merge_list(l1, l2):
	l1.next = None
	l2.next = None
	dummy = Node(-11)
	cur = dummy
	while l1 and l2:
		if l1.data < l2.data:
			cur.bottom = l1
			l1 = l1.bottom
		else:
			cur.bottom = l2
			l2 = l2.bottom
		cur = cur.bottom
	cur.bottom = l2 if not l1 else l1
	return dummy.bottom


def merge(head1, head2):
	l1 = head1
	l2 = head2
	l3 = Node(-1)
	temp = l3
	while l1 and l2:
		if l1.data < l2.data:
			l3.bottom = Node(l1.data)
			l1 = l1.bottom
		else:
			l3.bottom = Node(l2.data)
			l2 = l2.bottom
		l3 = l3.bottom
	if not l1:
		l3.bottom = l2
	if not l2:
		l3.bottom = l1
	return temp.bottom

def flatten(head):
	if not head or not head.next:
		return head
	head.next = flatten(head.next)
	result = merge(head, head.next)
	return result


def flatten(root):

	def merge(l1, l2):
		if l1.data > l2.data:
			(l1, l2) = (l2, l1)
		res = l1
		while l1 and l2:
			temp = l1
			while l1 and l1.data <= l2.data:
				temp = l1
				l1 = l1.bottom
			temp.bottom = l2
			(l1, l2) = (l2, l1)
		res.next = None
		return res

	def flattenHelper(root):
		if root is None or root.next is None:
			return root
		root.next = flattenHelper(root.next)
		return merge(root, root.next)
	return flattenHelper(root)


def flatten(root):
	p = root
	arr = []
	while p != None:
		q = p
		while q != None:
			arr.append(q.data)
			q = q.bottom
		p = p.next
	arr.sort()
	p = Node(arr[0])
	head = p
	arr.pop(0)
	while arr:
		p.bottom = Node(arr.pop(0))
		p = p.bottom
	return head


import sys

def helper(cur):
	if cur is None:
		return
	helper(cur.next)
	helper(cur.bottom)
	prev = cur
	hr = cur.next
	vr = cur.bottom
	while hr and vr:
		if vr.data <= hr.data:
			prev = vr
			vr = vr.bottom
		else:
			nxt = hr.bottom
			hr.bottom = vr
			prev.bottom = hr
			prev = hr
			hr = nxt
	while hr:
		prev.bottom = hr
		prev = hr
		hr = hr.bottom
	cur.next = None

def flatten(root):
	sys.setrecursionlimit(100000)
	helper(root)
	return root


def mergeList(head1, head2):
	head = Node(0)
	tmp = head
	while head1 and head2:
		if head1.data < head2.data:
			tmp.bottom = head1
			head1 = head1.bottom
		else:
			tmp.bottom = head2
			head2 = head2.bottom
		tmp = tmp.bottom
	if head1:
		tmp.bottom = head1
	else:
		tmp.bottom = head2
	return head.bottom

def flatten(root):
	if not root or not root.next:
		return root
	root.next = flatten(root.next)
	return mergeList(root, root.next)


def flatten_merge(head):
	next_node = head.next
	c1 = head
	c2 = next_node
	t = None
	l = None
	while True:
		if c1 == None:
			l.bottom = c2
			break
		if c2 == None:
			break
		if c1.data <= c2.data:
			l = c1
			c1 = c1.bottom
		else:
			l.bottom = c2
			c2 = c2.bottom
			l.bottom.bottom = c1
			l = l.bottom
	head.next = next_node.next
	return head

def flatten(root):
	current = head
	while current.next != None:
		next_node = current.next
		if current.data <= next_node.data:
			pass
		else:
			temp = next_node.next
			current.next = temp
			next_node.next = current
			current = next_node
		current = flatten_merge(current)
	return current


def flatten(root):

	def mergeTwoLists(l1, l2):
		if not l1 or not l2:
			return l1 is l1 or l2
		dummy = curr = Node(None)
		while l1 and l2:
			if l1.data <= l2.data:
				curr.bottom = l1
				l1 = l1.bottom
			else:
				curr.bottom = l2
				l2 = l2.bottom
			curr = curr.bottom
		if l1 or l2:
			curr.bottom = l1 if l1 else l2
		return dummy.bottom
	if not root:
		return root
	curr = root
	while curr and curr.next:
		next = curr.next.next
		curr = mergeTwoLists(curr, curr.next)
		curr.next = next
	return root


class Node:

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

def merge(a, b):
	if a is None:
		return b
	if b is None:
		return a
	result = None
	if a.data < b.data:
		result = a
		result.bottom = merge(a.bottom, b)
	else:
		result = b
		result.bottom = merge(a, b.bottom)
	result.next = None
	return result

def flatten(root):
	if root is None or root.next is None:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def merge(a, b):
	c = None
	if a is None:
		return b
	elif b is None:
		return a
	if a.data <= b.data:
		c = a
		c.bottom = merge(a.bottom, b)
	else:
		c = b
		c.bottom = merge(a, b.bottom)
	return c

def flatten(root):
	if root is None or root.next is None:
		return root
	return merge(root, flatten(root.next))


def flatten(root):
	if root.next == None:
		return root
	a = flatten(root.next)
	return merge(root, a)

def merge(node, a):
	res = Node(0)
	d = res
	while node and a:
		if node.data > a.data:
			d.bottom = a
			d = d.bottom
			a = a.bottom
		else:
			d.bottom = node
			d = d.bottom
			node = node.bottom
	if node:
		d.bottom = node
	else:
		d.bottom = a
	return res.bottom


def printf(node):
	s = ' '
	temp = node
	while temp:
		s += str(temp.data) + ' '
		temp = temp.bottom
	print(s)

def merge_sort(node1, node2):
	(temp1, temp2) = (node1, node2)
	headnode = Node(None)
	temp = headnode
	while temp1 and temp2:
		if temp1.data < temp2.data:
			temp.bottom = Node(temp1.data)
			temp = temp.bottom
			temp1 = temp1.bottom
		else:
			temp.bottom = Node(temp2.data)
			temp = temp.bottom
			temp2 = temp2.bottom
	if temp2:
		while temp2:
			temp.bottom = Node(temp2.data)
			temp = temp.bottom
			temp2 = temp2.bottom
	if temp1:
		while temp1:
			temp.bottom = Node(temp1.data)
			temp = temp.bottom
			temp1 = temp1.bottom
	return headnode.bottom

def flatten(root):
	temp1 = root
	temp2 = temp1.next
	if not temp2:
		return temp1
	temp3 = temp2.next
	while temp3 and temp1 and temp2:
		temp2.next = None
		temp1.next = None
		sorted_list = merge_sort(temp1, temp2)
		temp1 = sorted_list
		temp2 = temp3
		temp3 = temp3.next
	main = merge_sort(temp1, temp2)
	return main
	return root


def flatten(root):
	nn = root.next
	while nn is not None:
		sec = nn
		nn = nn.next
		sec.next = None
		root = merge(root, sec)
	return root

def merge(l1, l2):
	n = Node(0)
	tmp = n
	while l1 and l2:
		if l1.data <= l2.data:
			tmp.bottom = l1
			l1 = l1.bottom
		else:
			tmp.bottom = l2
			l2 = l2.bottom
		tmp = tmp.bottom
	if l1:
		tmp.bottom = l1
	if l2:
		tmp.bottom = l2
	return n.bottom


def flatten(root):
	head = Node(root.data)
	temp = head
	start = root
	q = []
	if start.next != None:
		q.append(start.next)
	if start.bottom != None:
		q.append(start.bottom)
	while len(q) != 0:
		l = 10 ** 9
		n = None
		index = None
		for (ind, i) in enumerate(q):
			if i.data < l:
				l = i.data
				index = ind
		next = q.pop(index)
		temp.bottom = next
		temp = next
		if temp.next != None:
			q.append(temp.next)
		if temp.bottom != None:
			q.append(temp.bottom)
	return head
	return root


def merge(a, b):
	ans = Node(0)
	res = ans
	while a and b:
		if a.data < b.data:
			ans.bottom = a
			a = a.bottom
		else:
			ans.bottom = b
			b = b.bottom
		ans = ans.bottom
	while a:
		ans.bottom = a
		a = a.bottom
		ans = ans.bottom
	while b:
		ans.bottom = b
		b = b.bottom
		ans = ans.bottom
	ans.next = None
	return res.bottom

def flatten(root):
	if root.next is None:
		return root
	k = flatten(root.next)
	return merge(root, k)


def merge(a, b):
	dummy = Node(0)
	res = dummy
	while a and b:
		if a.data < b.data:
			dummy.bottom = a
			a = a.bottom
		else:
			dummy.bottom = b
			b = b.bottom
		dummy = dummy.bottom
	if a:
		dummy.bottom = a
	if b:
		dummy.bottom = b
	return res.bottom

def flatten(root):
	if not root or not root.next:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def flatten(root):
	dummy = Node(0)
	node = root
	while node:
		sub_node = node
		new_list = dummy
		while new_list.bottom and sub_node:
			if new_list.bottom.data > sub_node.data:
				nxt = new_list.bottom
				new_list.bottom = sub_node
				sub_node = nxt
				new_list = new_list.bottom
			else:
				new_list = new_list.bottom
		if sub_node:
			new_list.bottom = sub_node
		node = node.next
	return dummy.bottom


def merge(left, right):
	if left is None:
		return right
	elif right is None:
		return left
	start = Node(0)
	temp = start
	while left and right:
		if left.data <= right.data:
			temp.bottom = left
			temp = left
			left = left.bottom
		else:
			temp.bottom = right
			temp = right
			right = right.bottom
	while left:
		temp.bottom = left
		temp = left
		left = left.bottom
	while right:
		temp.bottom = right
		temp = right
		right = right.bottom
	return start.bottom

def flatten(root):
	if root is None or root.next is None:
		return root
	root.next = flatten(root.next)
	new_root = merge(root, root.next)
	return new_root


def flatten(root):
	if root.next == None:
		return root
	nl = flatten(root.next)
	return merge(root, nl)

def merge(h1, h2):
	dummy = temp = Node(-1)
	while h1 != None and h2 != None:
		if h1.data < h2.data:
			temp.bottom = h1
			h1 = h1.bottom
		else:
			temp.bottom = h2
			h2 = h2.bottom
		temp = temp.bottom
	temp.bottom = h1 if h1 else h2
	return dummy.bottom


def convertBottom2Next(head):
	if head.bottom is None:
		return head
	temp = head
	while temp.bottom:
		temp.next = temp.bottom
		temp = temp.bottom
	return head

def mergeSortedLL(head1, head2):
	new_head = Node(float('-inf'))
	new_temp = new_head
	temp1 = head1
	temp2 = head2
	while temp1 and temp2:
		if temp1.data < temp2.data:
			new_temp.bottom = temp1
			temp1 = temp1.bottom
		else:
			new_temp.bottom = temp2
			temp2 = temp2.bottom
		new_temp = new_temp.bottom
	if temp1:
		new_temp.bottom = temp1
	if temp2:
		new_temp.bottom = temp2
	return new_head.bottom

def flatten(root):
	if root is None:
		return None
	if root.next is None:
		return convertBottom2Next(root)
	prev = None
	temp = root
	while temp:
		prev = mergeSortedLL(prev, temp)
		temp = temp.next
		prev.next = None
	return convertBottom2Next(prev)


def flatten(root):
	head = root
	a = root
	while a:
		temp = a.next
		while a.bottom:
			a = a.bottom
		a.bottom = temp
		a = a.bottom
	v = []
	while head is not None:
		v.append(head.data)
		head = head.bottom
	v.sort()
	result = Node(-1)
	temp = result
	for i in range(len(v)):
		result.bottom = Node(v[i])
		result = result.bottom
	temp = temp.bottom
	return temp


def flatten(root):

	def merge(left, right):
		if left == None:
			return right
		if right == None:
			return left
		ans = Node(-1)
		temp = ans
		while left and right:
			if left.data < right.data:
				temp.bottom = left
				temp = left
				left = left.bottom
			else:
				temp.bottom = right
				temp = right
				right = right.bottom
		if left:
			temp.bottom = left
		if right:
			temp.bottom = right
		return ans.bottom
	if not root:
		return -1
	if not root.next:
		return root
	dummy1 = merge(root, root.next)
	root = root.next.next
	while root:
		dummy1 = merge(dummy1, root)
		root = root.next
	return dummy1


def mergetwolist(head1, head2):
	start = Node(0)
	curr = start
	while head1 is not None and head2 is not None:
		if head1.data < head2.data:
			curr.bottom = head1
			curr = head1
			head1 = head1.bottom
		else:
			curr.bottom = head2
			curr = head2
			head2 = head2.bottom
	if head1 is None:
		head1 = head2
	curr.bottom = head1
	return start.bottom

def flatten(root):
	curr = root
	while curr is not None:
		if curr.bottom is not None and curr.next is not None:
			if curr.bottom.data < curr.next.data:
				curr.bottom.next = curr.next
				curr.next = None
				curr = curr.bottom
			else:
				curr.next.bottom = mergetwolist(curr.next.bottom, curr.bottom)
				curr.bottom = curr.next
				curr.next = None
				curr = curr.bottom
		elif curr.next is None:
			curr = curr.bottom
		else:
			curr.bottom = curr.next
			curr.next = None
			curr = curr.bottom
	return root


def merge(x, y):
	d = Node(0)
	res = d
	while x and y:
		if x.data < y.data:
			d.bottom = Node(x.data)
			x = x.bottom
		else:
			d.bottom = Node(y.data)
			y = y.bottom
		d = d.bottom
	if x:
		d.bottom = x
	else:
		d.bottom = y
	return res.bottom

def flatten(root):
	if root.next == None:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def flatten(root):
	cur = root.next
	head = root
	while cur:
		head = mergeSort(head, cur)
		cur = cur.next
	return head

def mergeSort(head1, head2):
	dummy_node = Node(0)
	pre = dummy_node
	cur1 = head1
	cur2 = head2
	while cur1 and cur2:
		if cur1.data >= cur2.data:
			pre.bottom = Node(cur2.data)
			cur2 = cur2.bottom
			pre = pre.bottom
		else:
			pre.bottom = Node(cur1.data)
			cur1 = cur1.bottom
			pre = pre.bottom
	while cur1:
		pre.bottom = Node(cur1.data)
		cur1 = cur1.bottom
		pre = pre.bottom
	while cur2:
		pre.bottom = Node(cur2.data)
		cur2 = cur2.bottom
		pre = pre.bottom
	return dummy_node.bottom


def flatten(root):
	if root.next == None or root == None:
		return root
	while root and root.next:
		temp = root.next.next
		root = merge_lists(root, root.next)
		root.next = temp
	return root

def merge_lists(first, second):
	dummy = Node(0)
	dummy_curr = dummy
	while first != None and second != None:
		if first.data <= second.data:
			dummy_curr.bottom = Node(first.data)
			dummy_curr = dummy_curr.bottom
			first = first.bottom
		else:
			dummy_curr.bottom = Node(second.data)
			dummy_curr = dummy_curr.bottom
			second = second.bottom
	while first != None:
		dummy_curr.bottom = Node(first.data)
		first = first.bottom
		dummy_curr = dummy_curr.bottom
	while second != None:
		dummy_curr.bottom = Node(second.data)
		second = second.bottom
		dummy_curr = dummy_curr.bottom
	return dummy.bottom


def mergel(root, other):
	dummy = temp = Node(-1)
	while root and other:
		if root.data < other.data:
			dummy.bottom = root
			root = root.bottom
		elif root.data > other.data:
			dummy.bottom = other
			other = other.bottom
		else:
			dummy.bottom = root
			root = root.bottom
		dummy = dummy.bottom
	if root == None:
		dummy.bottom = other
	else:
		dummy.bottom = root
	return temp.bottom

def flatten(root):
	if root == None or root.next == None:
		return root
	other = flatten(root.next)
	answer = mergel(root, other)
	return answer


def merge(root, other):
	dummy = temp = Node(-1)
	while root and other:
		if root.data > other.data:
			dummy.bottom = other
			other = other.bottom
		else:
			dummy.bottom = root
			root = root.bottom
		dummy = dummy.bottom
	remaining = root or other
	dummy.bottom = remaining
	return temp.bottom

def flatten(root):
	if not root or root.next is None:
		return root
	other = flatten(root.next)
	newhead = merge(root, other)
	return newhead


def flatten(root):
	head = root
	while head and head.next:
		if head.data <= head.next.data:
			(a, b) = (head, head.next)
		else:
			(a, b) = (head.next, head)
		while a:
			if not a.bottom:
				a.bottom = b
				break
			if not b:
				break
			if a.bottom.data > b.data:
				tmp = a.bottom
				a.bottom = b
				b = tmp
			a = a.bottom
		head.next = head.next.next
	return head


def merge(a, b):
	if not a:
		return b
	if not b:
		return a
	ans = None
	if a.data < b.data:
		ans = a
		ans.bottom = merge(a.bottom, b)
	else:
		ans = b
		ans.bottom = merge(a, b.bottom)
	return ans

def flatten(root):
	if not root:
		return None
	mergedLL = merge(root, flatten(root.next))
	return mergedLL


def flatten(root):
	L = []
	n = root
	while n is not None:
		n1 = n
		while n1 is not None:
			L.append(n1.data)
			n1 = n1.bottom
		n = n.next
	L.sort()
	n = root
	n.next = None
	n.bottom = None
	while L:
		a = L.pop(0)

		def add(a):
			new_node = Node(a)
			n.bottom = new_node
		add(a)
		n = n.bottom
	return root.bottom


def flatten(root):

	def recurseMerge(root):
		if root.next == None:
			return root
		l1 = root
		l2 = recurseMerge(root.next)
		dummy = Node(0)
		temp = dummy
		while l1 and l2:
			if l1.data <= l2.data:
				temp.bottom = l1
				l1 = l1.bottom
			else:
				temp.bottom = l2
				l2 = l2.bottom
			temp = temp.bottom
		while l1:
			temp.bottom = l1
			l1 = l1.bottom
			temp = temp.bottom
		while l2:
			temp.bottom = l2
			l2 = l2.bottom
			temp = temp.bottom
		return dummy.bottom
	root = recurseMerge(root)
	return root


def flatten(root):
	a = []
	while root:
		a.append(root.data)
		x = root.bottom
		while x:
			a.append(x.data)
			x = x.bottom
		root = root.next
	a = sorted(a)
	y = Node(0)
	x = y
	for i in a:
		x.bottom = Node(i)
		x = x.bottom
	return y.bottom


def flatten(root):
	if not root or (not root.next and (not root.bottom)):
		return root
	if root.next:
		root.next = flatten(root.next)
	root = merge(root, root.next)
	return root

def merge(a, b):
	if not a:
		return b
	if not b:
		return a
	if a.data < b.data:
		a.bottom = merge(a.bottom, b)
		return a
	else:
		b.bottom = merge(a, b.bottom)
		return b


class Node:

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

def flatten(root):
	if not root or (not root.next and (not root.bottom)):
		return root
	if root.next:
		root.next = flatten(root.next)
	root = merge(root, root.next)
	return root

def merge(a, b):
	if not a:
		return b
	if not b:
		return a
	if a.data < b.data:
		a.bottom = merge(a.bottom, b)
		return a
	else:
		b.bottom = merge(a, b.bottom)
		return b


class Node:

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

def merge(a, b):
	if a is None:
		return b
	if b is None:
		return a
	if a.data < b.data:
		result = a
		result.bottom = merge(a.bottom, b)
	else:
		result = b
		result.bottom = merge(a, b.bottom)
	return result

def flatten(head):
	if head is None or head.next is None:
		return head
	head.next = flatten(head.next)
	head = merge(head, head.next)
	return head

def print_list(head):
	while head:
		print(head.data, end=' ')
		head = head.bottom


def flatten(head):
	while head.next != None:
		b = head.next
		while b != None:
			a = head.bottom
			prev_a = head
			t = Node(b.data)
			while a != None and b.data > a.data:
				prev_a = a
				a = a.bottom
			t.bottom = a
			prev_a.bottom = t
			g = head
			b = b.bottom
		head.next = head.next.next
	return head


def flatten(root):
	if root.next is None:
		return root
	nextroot = flatten(root.next)
	root.next = None
	return merge(root, nextroot)

def merge(cur1, cur2):
	head = Node(0)
	temp = head
	while cur1 is not None and cur2 is not None:
		if cur1.data < cur2.data:
			temp.bottom = cur1
			cur1 = cur1.bottom
		else:
			temp.bottom = cur2
			cur2 = cur2.bottom
		temp = temp.bottom
	if cur1 is None:
		temp.bottom = cur2
	else:
		temp.bottom = cur1
	return head.bottom


def merge(a, b):
	if a == None:
		return b
	if b == None:
		return a
	result = None
	if a.data < b.data:
		result = a
		result.bottom = merge(a.bottom, b)
	else:
		result = b
		result.bottom = merge(a, b.bottom)
	result.next = None
	return result

def flatten(root):
	if root == None or root.next == None:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def flatten(root):
	result = root
	while result.next:
		curr = result
		l2 = result.next
		l1 = result.bottom
		nextp = l2.next
		while l1 and l2:
			if l1.data <= l2.data:
				curr.bottom = l1
				curr = l1
				l1 = l1.bottom
			else:
				curr.bottom = l2
				curr = l2
				l2 = l2.bottom
		while l1:
			curr.bottom = l1
			curr = l1
			l1 = l1.bottom
		while l2:
			curr.bottom = l2
			curr = l2
			l2 = l2.bottom
		result.next = nextp
	return result


def flatten(root):
	temp = root
	l = []
	while temp != None:
		l.append(temp.data)
		temp2 = temp.bottom
		while temp2 != None:
			l.append(temp2.data)
			temp2 = temp2.bottom
		temp = temp.next
	l.sort()
	l3 = Node(None)
	temp3 = l3
	i = 0
	while i < len(l):
		new = Node(l[i])
		temp3.bottom = new
		temp3 = temp3.bottom
		i += 1
	return l3.bottom


def flatten(root):
	if root is None or root.next is None:
		return root
	left = root
	right = flatten(root.next)
	res = merge(left, right)
	return res

def merge(left, right):
	dummy_node = Node(0)
	prev = dummy_node
	while True:
		if left is None:
			prev.bottom = right
			break
		if right is None:
			prev.bottom = left
			break
		if left.data <= right.data:
			prev.bottom = left
			left = left.bottom
			prev = prev.bottom
		else:
			prev.bottom = right
			right = right.bottom
			prev = prev.bottom
	return dummy_node.bottom


def func(root):
	if root.next is None:
		return root
	if root.next:
		y = func(root.next)
	temp = root
	head2 = Node(0)
	prev = head2
	while y and temp:
		if temp.data <= y.data:
			prev.bottom = temp
			temp = temp.bottom
			prev = prev.bottom
		else:
			prev.bottom = y
			y = y.bottom
			prev = prev.bottom
	if temp:
		prev.bottom = temp
		prev = prev.bottom
	if y:
		prev.bottom = y
	return head2.bottom

def flatten(root):
	func(root)
	return root


class Node:

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

def flatten(root):
	if not root or not root.next:
		return root
	root.next = flatten(root.next)
	root = mergeTwoLists(root, root.next)
	return root

def mergeTwoLists(list1, list2):
	if not list1:
		return list2
	if not list2:
		return list1
	c = dummy = Node(0)
	while list1 and list2:
		if list1.data > list2.data:
			c.bottom = list2
			list2 = list2.bottom
			c = c.bottom
		else:
			c.bottom = list1
			list1 = list1.bottom
			c = c.bottom
	if list1:
		c.bottom = list1
	else:
		c.bottom = list2
	return dummy.bottom


def flatten(root):
	temp = root
	a = []
	while temp:
		temp2 = temp
		while temp2:
			a.append(temp2.data)
			temp2 = temp2.bottom
		if temp.bottom == None:
			a.append(temp.data)
		temp = temp.next
	a.sort()
	temp = root
	i = 0
	while temp:
		temp2 = temp
		while temp2:
			temp2.data = a[i]
			i += 1
			temp2 = temp2.bottom
		if temp.bottom == None:
			temp.data = a[i]
			i += 1
		temp = temp.next
	temp = root
	while temp:
		temp2 = temp
		while temp2.bottom:
			temp2 = temp2.bottom
		temp = temp.next
		temp2.bottom = temp
	return root


def flatten(root):
	lst = []
	while root:
		lst.append(root.data)
		node = root
		while node.bottom:
			lst.append(node.bottom.data)
			node = node.bottom
		root = root.next
	lst.sort()
	head = Node(lst[0])
	cur = head
	for i in range(1, len(lst)):
		node = Node(lst[i])
		cur.bottom = node
		cur = node
	return head


def flatten(root):
	cur = root
	nex = root.next
	cur.next = None
	while nex != None:
		l1 = cur
		l2 = nex
		while l1 != None and l2 != None:
			temp = None
			while l1 != None and l1.data <= l2.data:
				temp = l1
				l1 = l1.bottom
			temp.bottom = l2
			(l1, l2) = (l2, l1)
		nex = nex.next
	return root


def mergeTwo(head1, head2):
	dummy_node = Node(0)
	pre = dummy_node
	cur1 = head1
	cur2 = head2
	while cur1 and cur2:
		if cur1.data >= cur2.data:
			pre.bottom = Node(cur2.data)
			cur2 = cur2.bottom
			pre = pre.bottom
		else:
			pre.bottom = Node(cur1.data)
			cur1 = cur1.bottom
			pre = pre.bottom
	while cur1:
		pre.bottom = Node(cur1.data)
		cur1 = cur1.bottom
		pre = pre.bottom
	while cur2:
		pre.bottom = Node(cur2.data)
		cur2 = cur2.bottom
		pre = pre.bottom
	return dummy_node.bottom

def flatten(root):
	cur = root
	cur = cur.next
	while cur is not None:
		root = mergeTwo(root, cur)
		cur = cur.next
	return root


class Node:

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

def flatList(root, right):
	newRoot = Node(0)
	newTemp = newRoot
	arr = []
	while root and right:
		if root.data <= right.data:
			newTemp.bottom = root
			arr.append(root.data)
			temp = root
			root = root.bottom
			newTemp = newTemp.bottom
		else:
			newTemp.bottom = right
			arr.append(right.data)
			temp = right
			right = right.bottom
			newTemp = newTemp.bottom
	while root:
		newTemp.bottom = root
		arr.append(root.data)
		newTemp = newTemp.bottom
		root = root.bottom
	while right:
		newTemp.bottom = right
		arr.append(right.data)
		newTemp = newTemp.bottom
		right = right.bottom
	return newRoot.bottom

def flatten(root):
	newRoot = Node(0)
	curr = root
	right = root.next
	while curr:
		newList = flatList(curr, right)
		curr = newList
		newRoot.bottom = newList
		if right and right.next:
			right = right.next
		else:
			break
	return newRoot.bottom


class Node:

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

def flatten(root):

	def merge(one, two):
		res = Node(0)
		head = res
		while one and two:
			if one.data < two.data:
				res.bottom = one
				one = one.bottom
			else:
				res.bottom = two
				two = two.bottom
			res = res.bottom
		while one:
			res.bottom = one
			one = one.bottom
			res = res.bottom
		while two:
			res.bottom = two
			two = two.bottom
			res = res.bottom
		return head.bottom

	def flat(node):
		if node == None or node.next == None:
			return node
		node.next = flat(node.next)
		node = merge(node, node.next)
		return node
	return flat(root)


def flatten(root):
	ptr = root.next
	root.next = None
	while ptr:
		down = ptr
		temp = root.bottom
		root.bottom = down
		while down.bottom:
			down = down.bottom
		down.bottom = temp
		temp = ptr
		ptr = ptr.next
		temp.next = None
	ptr1 = root
	while ptr1:
		ptr2 = ptr1
		while ptr2:
			if ptr2.data < ptr1.data:
				(ptr1.data, ptr2.data) = (ptr2.data, ptr1.data)
			ptr2 = ptr2.bottom
		ptr1 = ptr1.bottom
	return root


def sortedMerge(head1, head2):
	if not head2:
		return head1
	tmp = temp = None
	while head1 and head2:
		if head1.data <= head2.data:
			if not tmp:
				temp = head1
				tmp = head1
			else:
				tmp.bottom = head1
				tmp = tmp.bottom
			head1 = head1.bottom
		else:
			if not tmp:
				temp = head2
				tmp = head2
			else:
				tmp.bottom = head2
				tmp = tmp.bottom
			head2 = head2.bottom
	while head1:
		tmp.bottom = head1
		tmp = tmp.bottom
		head1 = head1.bottom
	while head2:
		tmp.bottom = head2
		tmp = tmp.bottom
		head2 = head2.bottom
	return temp

def flatten(root):
	temp = root
	root = root.next
	while root:
		temp = sortedMerge(temp, root)
		root = root.next
	return temp


def flatten(root):
	l = []
	head = None
	tail = None
	while root:
		temp = root
		while temp:
			l.append(temp.data)
			temp = temp.bottom
		root = root.next
	l.sort()
	for i in l:
		dat = Node(i)
		if head == None:
			head = dat
		else:
			tail.bottom = dat
		tail = dat
	return head


def merge_sort(head1, head2):
	dummy = Node(0)
	pre = dummy
	curr1 = head1
	curr2 = head2
	while curr1 and curr2:
		if curr1.data >= curr2.data:
			pre.bottom = Node(curr2.data)
			curr2 = curr2.bottom
			pre = pre.bottom
		else:
			pre.bottom = Node(curr1.data)
			curr1 = curr1.bottom
			pre = pre.bottom
	while curr1:
		pre.bottom = Node(curr1.data)
		curr1 = curr1.bottom
		pre = pre.bottom
	while curr2:
		pre.bottom = Node(curr2.data)
		curr2 = curr2.bottom
		pre = pre.bottom
	return dummy.bottom

def flatten(root):
	cur = root.next
	head = root
	while cur:
		head = merge_sort(head, cur)
		cur = cur.next
	return head


s = []

def recur(root):
	global s
	if root == None:
		return
	else:
		recur(root.next)
		recur(root.bottom)
		s.append(root.data)

def flatten(root):
	global s
	recur(root)
	s = sorted(s)
	k = Node(s[0])
	uu = k
	for i in range(1, len(s)):
		p = Node(s[i])
		k.bottom = p
		k = k.bottom
	s = []
	return uu


def flatten(root):
	l = []
	h = root
	while h:
		l.append(h.data)
		h1 = h.bottom
		while h1:
			l.append(h1.data)
			h1 = h1.bottom
		h = h.next
	l.sort()
	a = b = Node(-1)
	for i in l:
		a.bottom = Node(i)
		a = a.bottom
	return b.bottom


class Node:

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

def merge(a, b):
	temp = Node(0)
	res = temp
	while a != None and b != None:
		if a.data <= b.data:
			temp.bottom = a
			temp = temp.bottom
			a = a.bottom
		else:
			temp.bottom = b
			temp = temp.bottom
			b = b.bottom
	if a != None:
		temp.bottom = a
	else:
		temp.bottom = b
	return res.bottom

def flatten(root):
	if root is None or root.next is None:
		return root
	root.next = flatten(root.next)
	root = merge(root, root.next)
	return root


def flatten(root):

	def merge(a, b):
		temp = Node(0)
		res = temp
		while a != None and b != None:
			if a.data < b.data:
				temp.bottom = a
				temp = temp.bottom
				a = a.bottom
			else:
				temp.bottom = b
				temp = temp.bottom
				b = b.bottom
		if a:
			temp.bottom = a
		else:
			temp.bottom = b
		return res.bottom
	p1 = None
	while root:
		nes = root.next
		root.next = root.bottom
		p2 = root
		p1 = merge(p1, p2)
		root = nes
	return p1


def merge(h1, h2):
	if not h1:
		return h2
	if not h2:
		return h1
	l1 = h1
	l2 = h2
	newHead = Node(-1)
	temp = newHead
	while l1 and l2:
		if l1.data < l2.data:
			temp.bottom = l1
			l1 = l1.next
		else:
			temp.bottom = l2
			l2 = l2.bottom
		temp = temp.bottom
	if not l1:
		temp.bottom = l2
	else:
		temp.bottom = l1
	return newHead.bottom

def flatten(root):
	if not root:
		return
	l1 = flatten(root.next)
	l2 = root.bottom
	root.bottom = merge(l1, l2)
	return root