Given Pointer/Reference to the head of the linked list, the task is to Sort the given linked list using Merge Sort.
Note: If the length of linked list is odd, then the extra node should go in the first list while splitting.
Example 1:
Input:
N = 5
value[]  = {3,5,2,4,1}
Output: 1 2 3 4 5
Explanation: After sorting the given
linked list, the resultant matrix
will be 1->2->3->4->5.
Example 2:
Input:
N = 3
value[]  = {9,15,0}
Output: 0 9 15
Explanation: After sorting the given
linked list , resultant will be
0->9->15.
Your Task:
For C++ and Python: The task is to complete the function mergeSort() which sort the linked list using merge sort function.
For Java: The task is to complete the function mergeSort() and return the node which can be used to print the sorted linked list.
Expected Time Complexity: O(N*Log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



'''

    :param head: head of unsorted linked list 

    :return: head of sorted linkd list

    

    # Node Class

    class Node:

        def __init__(self, data):  # data -> value stored in node

            self.data = data

            self.next = None

'''

class Solution:

    #Function to sort the given linked list using Merge Sort.

    def mergeSort(self, head):

        

Solutions:
class Solution:

	def mergeSort(self, head):
		res = []
		while head:
			res.append(head.data)
			head = head.next
		res.sort()
		ans = Node(res[0])
		curr = ans
		for i in range(1, len(res)):
			val = Node(res[i])
			curr.next = val
			curr = val
		return ans


class Solution:

	def findsize(self, temp):
		s = temp
		f = temp.next
		while f and f.next:
			s = s.next
			f = f.next.next
		return s

	def merge(self, left, right):
		curr1 = left
		curr2 = right
		val = Node(-1)
		temp = val
		while curr1 and curr2:
			if curr1.data < curr2.data:
				val.next = Node(curr1.data)
				curr1 = curr1.next
			else:
				val.next = Node(curr2.data)
				curr2 = curr2.next
			val = val.next
		if not curr1:
			val.next = curr2
		if not curr2:
			val.next = curr1
		return temp.next

	def mergeSort(self, head):
		if not head or not head.next:
			return head
		mid = self.findsize(head)
		left = head
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		res = self.merge(left, right)
		return res


class Solution:

	def findmid(self, temp):
		s = temp
		f = temp.next
		while f and f.next:
			s = s.next
			f = f.next.next
		return s

	def merge(self, left, right):
		l1 = left
		l2 = right
		l3 = Node(-1)
		temp = l3
		while l1 and l2:
			if l1.data < l2.data:
				l3.next = Node(l1.data)
				l1 = l1.next
			else:
				l3.next = Node(l2.data)
				l2 = l2.next
			l3 = l3.next
		if not l1:
			l3.next = l2
		if not l2:
			l3.next = l1
		return temp.next

	def mergeSort(self, head):
		if not head or not head.next:
			return head
		mid = self.findmid(head)
		left = head
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		result = self.merge(left, right)
		return result


import math

class Solution:

	def merge(self, left, right):
		result = None
		res_head = None
		while left is not None and right is not None:
			if left.data > right.data:
				if result is None:
					result = right
					res_head = right
				else:
					result.next = right
					result = result.next
				right = right.next
				result.next = None
			else:
				if result is None:
					result = left
					res_head = left
				else:
					result.next = left
					result = result.next
				left = left.next
				result.next = None
		if left is not None:
			result.next = left
		if right is not None:
			result.next = right
		return res_head

	def mergeSort(self, head):
		if head.next is None:
			return head
		else:
			n = 0
			front = head
			while front is not None:
				front = front.next
				n += 1
			c = math.ceil(n / 2)
			front = head
			prev = None
			while c > 0:
				prev = front
				front = front.next
				c -= 1
			prev.next = None
			left = self.mergeSort(head)
			right = self.mergeSort(front)
			return self.merge(left, right)


class Solution:

	def find_mid(self, head):
		slow = head
		fast = head.next
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		return slow

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

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		mid = self.find_mid(head)
		left = head
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		result = self.merge(left, right)
		return result


class Solution:

	def Findmid(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		return slow

	def merge(self, l, r):
		ans = Node(0)
		temp = ans
		if l is None:
			return r
		if r is None:
			return l
		while l and r:
			if l.data <= r.data:
				temp.next = l
				temp = l
				l = l.next
			else:
				temp.next = r
				temp = r
				r = r.next
		if l:
			while l:
				temp.next = l
				temp = l
				l = l.next
		if r:
			while r:
				temp.next = r
				temp = r
				r = r.next
		return ans.next

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		temp = head
		fast = head
		slow = head
		while fast and fast.next:
			temp = slow
			slow = slow.next
			fast = fast.next.next
		temp.next = None
		l = self.mergeSort(head)
		r = self.mergeSort(slow)
		res = self.merge(l, r)
		return res


class Solution:

	def mergeSort(self, head):
		a = []
		while head is not None:
			a.append(head.data)
			head = head.next
		a.sort()
		a.append('x')
		head = None
		tail = None
		for ele in a:
			if ele != 'x':
				if head is None:
					newnode = Node(ele)
					head = newnode
					tail = newnode
				else:
					newnode = Node(ele)
					tail.next = newnode
					tail = newnode
		return head


class Solution:

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		middle = self.getMiddle(head)
		next_to_middle = middle.next
		middle.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(next_to_middle)
		result = self.sortedMerge(left, right)
		return result

	def getMiddle(self, head):
		if head == None:
			return head
		slow = head
		fast = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

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


class Solution:

	def mergeSort(self, head):
		if not head or not head.next:
			return head
		(slow, fast, prev) = (head, head, head)
		while fast and fast.next:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		mid = slow
		prev.next = None
		first = self.mergeSort(head)
		second = self.mergeSort(mid)
		head = self.mergetwolist(first, second)
		return head

	def mergetwolist(self, first, second):
		head = Node(0)
		tmp = head
		while first and second:
			if first.data < second.data:
				tmp.next = first
				first = first.next
			else:
				tmp.next = second
				second = second.next
			tmp = tmp.next
		if first:
			tmp.next = first
		if second:
			tmp.next = second
		return head.next


class Solution:

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


class Solution:

	def mergeSort(self, head):
		if not head or head.next == None:
			return head
		middle = self.get_middle(head)
		nexttomiddle = middle.next
		middle.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(nexttomiddle)
		Sortedlist = self.Sort_two(left, right)
		return Sortedlist

	def get_middle(self, head):
		if head == None:
			return head
		slow = head
		fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		return slow

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


class Solution:

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		slow = head
		fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		mid = slow
		next_mid = slow.next
		slow.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(next_mid)
		sorted_ll = self.sorte(left, right)
		return sorted_ll

	def sorte(self, left, right):
		result = None
		if left == right or left == None:
			return right
		if right == None:
			return left
		if left.data <= right.data:
			result = left
			result.next = self.sorte(left.next, right)
		else:
			result = right
			result.next = self.sorte(left, right.next)
		return result


class Solution:

	def mergeSort(self, head):

		def merge(temp1, temp2):
			if not temp1:
				return temp2
			if not temp2:
				return temp1
			temp = Node(0)
			h = temp
			while temp1 and temp2:
				if temp1.data <= temp2.data:
					temp.next = temp1
					temp = temp.next
					temp1 = temp1.next
				else:
					temp.next = temp2
					temp = temp.next
					temp2 = temp2.next
			if temp1:
				temp.next = temp1
			elif temp2:
				temp.next = temp2
			h = h.next
			return h

		def mergesort(head):
			if not head or not head.next:
				return head
			fast = head
			slow = head
			while fast and fast.next:
				temp = slow
				slow = slow.next
				fast = fast.next.next
			temp.next = None
			left = mergesort(head)
			right = mergesort(slow)
			return merge(left, right)
		return mergesort(head)


class Solution:

	def mergeSort(self, head):

		def sortedMerge(left, right):
			if not left:
				return right
			if not right:
				return left
			ans = Node(-1)
			temp = ans
			while left and right:
				if left.data < right.data:
					temp.next = left
					temp = left
					left = left.next
				else:
					temp.next = right
					temp = right
					right = right.next
			if left:
				temp.next = left
			if right:
				temp.next = right
			return ans.next

		def findMiddle(head):
			slow = head
			fast = head.next
			while fast and fast.next:
				slow = slow.next
				fast = fast.next.next
			return slow
		if head is None or head.next is None:
			return head
		mid = findMiddle(head)
		left = head
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		result = sortedMerge(left, right)
		return result


class Solution:

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		middle = self.getmiddle(head)
		nextmiddle = middle.next
		middle.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(nextmiddle)
		sortedlist = self.merge(left, right)
		return sortedlist

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

	def getmiddle(self, head):
		if head == None:
			return head
		slow = head
		fast = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow


class Node:

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

class Solution:

	def mergeSort(self, head):
		temp = head
		lst = []
		while temp:
			lst.append(temp.data)
			temp = temp.next
		res1 = Node(0)
		res2 = res1
		lst.sort()
		for num in lst:
			res1.next = Node(num)
			res1 = res1.next
		return res2.next


class Solution:

	def get_mid(self, head):
		try:
			slow = head
			fast = head.next
			while fast and fast.next:
				slow = slow.next
				fast = fast.next.next
			return slow
		except Exception as e:
			print('get_mid: ', e)

	def merge(self, head1, head2):
		try:
			temp1 = head1
			temp2 = head2
			new_head = new_tail = None
			while temp1 and temp2:
				if temp1.data <= temp2.data:
					if new_head is None:
						new_head = new_tail = temp1
					else:
						new_tail.next = temp1
						new_tail = temp1
					temp1 = temp1.next
				else:
					if new_head is None:
						new_head = new_tail = temp2
					else:
						new_tail.next = temp2
						new_tail = temp2
					temp2 = temp2.next
			if temp1:
				new_tail.next = temp1
				new_tail = temp1
			if temp2:
				new_tail.next = temp2
				new_tail = temp2
			return new_head
		except Exception as e:
			print('merge: ', e)

	def mergeSort(self, head):
		try:
			if head is None or head.next is None:
				return head
			else:
				mid = self.get_mid(head)
				left_head = head
				right_head = mid.next
				mid.next = None
				left_head = self.mergeSort(left_head)
				right_head = self.mergeSort(right_head)
				head = self.merge(left_head, right_head)
				return head
		except Exception as e:
			print('mergeSort: ', e)


class Solution:

	def mergeSort(self, head):

		def sort(head):
			n = 0
			flag = False
			mid = None
			tail = head
			while tail:
				tail = tail.next
				if flag:
					mid = mid.next if mid else head
				flag = not flag
				n += 1
			if n == 1:
				return head
			if n % 2 != 0:
				mid = mid.next
			n1 = head
			n2 = mid.next
			mid.next = None
			n1 = sort(n1)
			n2 = sort(n2)
			n3 = None
			n3_t = None
			while n1 and n2:
				if n1.data > n2.data:
					(n1, n2) = (n2, n1)
				node = n1
				n1 = n1.next
				node.next = None
				if n3:
					n3_t.next = node
					n3_t = n3_t.next
				else:
					n3 = node
					n3_t = n3
			if n1 == None:
				n1 = n2
				n2 = None
			if n2 == None:
				if n3_t:
					n3_t.next = n1
				else:
					n3 = n1
			return n3
		return sort(head)


class Solution:

	def mergeSort(self, head):

		def getMiddle(head):
			if head is None:
				return None
			slow = head
			fast = head
			while fast.next is not None and fast.next.next is not None:
				slow = slow.next
				fast = fast.next.next
			return slow

		def mergeLists(left, right):
			dummy = Node(0)
			tail = dummy
			while left and right:
				if left.data <= right.data:
					tail.next = left
					left = left.next
				else:
					tail.next = right
					right = right.next
				tail = tail.next
			tail.next = left or right
			return dummy.next
		if head is None or head.next is None:
			return head
		mid = getMiddle(head)
		left = head
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		return mergeLists(left, right)


class Solution:

	def mergeSort(self, head):
		l = []
		t = head
		while t:
			l.append(t.data)
			t = t.next
		l.sort()
		h = head
		i = 0
		while h:
			h.data = l[i]
			h = h.next
			i = i + 1
		return head


class Solution:

	def mergeSort(self, head):
		arr = []
		cur = head
		prev = None
		while cur is not None:
			prev = cur
			cur = cur.next
			prev.next = None
			arr.append(prev)
		return self.LinkedListMergeSort(0, len(arr) - 1, arr)

	def LinkedListMergeSort(self, l, h, arr):
		if l < h:
			m = (l + h) // 2
			arr[l] = self.LinkedListMergeSort(l, m, arr)
			arr[h] = self.LinkedListMergeSort(m + 1, h, arr)
			arr[l] = arr[h] = self.merge(arr[l], arr[h], arr)
		return arr[l]

	def merge(self, temp1, temp2, arr):
		head = Node(0)
		temp = head
		while temp1 is not None and temp2 is not None:
			if temp1.data < temp2.data:
				temp.next = temp1
				temp1 = temp1.next
			else:
				temp.next = temp2
				temp2 = temp2.next
			temp = temp.next
		if temp1 is None:
			temp.next = temp2
		else:
			temp.next = temp1
		temp = head
		head = head.next
		del temp
		return head


class Solution:

	def mergeSort(self, head):
		a = []
		while head != None:
			a.append(head.data)
			head = head.next
		a.sort()
		for i in a:
			print(i, end=' ')


class Solution:

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


class Solution:

	def merge(self, cur, right):
		if cur == None:
			return right
		if right == None:
			return cur
		dummy = Node(-1)
		temp = dummy
		while cur and right:
			if cur.data < right.data:
				temp.next = cur
				temp = cur
				cur = cur.next
			else:
				temp.next = right
				temp = right
				right = right.next
		while right:
			temp.next = right
			temp = right
			right = right.next
		while cur:
			temp.next = cur
			temp = cur
			cur = cur.next
		return dummy.next

	def find_middle(self, head):
		slow = head
		fast = head.next
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		return slow

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		mid = self.find_middle(head)
		cur = head
		right = mid.next
		mid.next = None
		cur = self.mergeSort(cur)
		right = self.mergeSort(right)
		ans = self.merge(cur, right)
		return ans


def sortedMerge(head1, head2):
	temp = Node(-1)
	curr = temp
	while head1 and head2:
		if head1.data <= head2.data:
			curr.next = Node(head1.data)
			head1 = head1.next
			curr = curr.next
		else:
			curr.next = Node(head2.data)
			curr = curr.next
			head2 = head2.next
	while head1:
		curr.next = Node(head1.data)
		head1 = head1.next
		curr = curr.next
	while head2:
		curr.next = Node(head2.data)
		curr = curr.next
		head2 = head2.next
	return temp.next

def middle(head):
	if head == None:
		return head
	(slow, fast) = (head, head)
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	return slow

class Solution:

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		mid = middle(head)
		head2 = mid.next
		mid.next = None
		nhead1 = self.mergeSort(head)
		nhead2 = self.mergeSort(head2)
		fhead = sortedMerge(nhead1, nhead2)
		return fhead


class Solution:

	def getmid(self, head):
		c = 0
		cur = head
		while head != None:
			c += 1
			head = head.next
		if c % 2 == 0:
			i = c // 2
		else:
			i = c // 2 + 1
		for j in range(1, i):
			cur = cur.next
		return cur

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

	def mergeSort(self, head):
		cur = head
		if head == None or head.next == None:
			return head
		middle = self.getmid(head)
		nextmid = middle.next
		middle.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(nextmid)
		sorted_list = self.SortMerge(left, right)
		return sorted_list


class Solution:

	def middle(self, temp):
		(hare, tort) = (temp, temp)
		while hare and hare.next and hare.next.next:
			hare = hare.next.next
			tort = tort.next
		return tort

	def sort(self, l, r):
		merged = Node(-1)
		temp = merged
		while l and r:
			if l.data < r.data:
				temp.next = l
				l = l.next
			else:
				temp.next = r
				r = r.next
			temp = temp.next
		while l:
			temp.next = l
			l = l.next
			temp = temp.next
		while r:
			temp.next = r
			r = r.next
			temp = temp.next
		return merged.next

	def mergeSort(self, head):
		if not head or not head.next:
			return head
		mid = self.middle(head)
		nxt = mid.next
		mid.next = None
		return self.sort(self.mergeSort(head), self.mergeSort(nxt))


class Solution:

	def mergeSort(self, head):
		dummy = Node(-1)
		res = dummy
		st = []
		curr = head
		while curr:
			st.append(curr.data)
			curr = curr.next
		st.sort()
		for i in range(len(st)):
			res.next = Node(st[i])
			res = res.next
		return dummy.next


class Solution:

	def mergeSort(self, head):
		curr = head
		if head == None or head.next == None:
			return head
		mid = Solution().find_mid(head)
		left = head
		right = mid.next
		mid.next = None
		head1 = Solution().mergeSort(left)
		head2 = Solution().mergeSort(right)
		return Solution().merge(head1, head2)

	def find_mid(self, head):
		if head and head.next:
			slow = head
			fast = head.next
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		if fast and fast.next:
			return slow.next
		else:
			return slow

	def merge(self, head1, head2):
		curr1 = head1
		curr2 = head2
		head = None
		curr = None
		while curr1 and curr2:
			if curr1.data < curr2.data:
				node = curr1
				curr1 = curr1.next
			else:
				node = curr2
				curr2 = curr2.next
			if head == None:
				head = node
			else:
				curr.next = node
			curr = node
		if curr1:
			if head == None:
				head = curr1
			else:
				curr.next = curr1
		if curr2:
			if head == None:
				head = curr2
			else:
				curr.next = curr2
		return head


class Node:

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

class Solution:

	def mergeSort(self, head):
		if head.next == None:
			return head
		mid = self.findMid(head)
		head2 = mid.next
		mid.next = None
		newhead1 = self.mergeSort(head)
		newhead2 = self.mergeSort(head2)
		finalhead = self.merge(newhead1, newhead2)
		return finalhead

	def merge(self, head1, head2):
		merged = Node(-1)
		temp = merged
		while head1 != None and head2 != None:
			if head1.data < head2.data:
				temp.next = head1
				head1 = head1.next
			else:
				temp.next = head2
				head2 = head2.next
			temp = temp.next
		while head1 != None:
			temp.next = head1
			head1 = head1.next
			temp = temp.next
		while head2 != None:
			temp.next = head2
			head2 = head2.next
			temp = temp.next
		return merged.next

	def findMid(self, head):
		slow = head
		fast = head.next
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow


class Solution:

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		mid = self.getMid(head)
		new_mid = mid.next
		mid.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(new_mid)
		res = self.merge(left, right)
		return res

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

	def getMid(self, head):
		(slow, fast) = (head, head)
		while fast.next is not None and fast.next.next is not None:
			slow = slow.next
			fast = fast.next.next
		return slow


def sortedMerge(head1, head2):
	if head1.data > head2.data:
		p = head2
		end = head2
		store = head1
	else:
		p = head1
		end = head1
		store = head2
	while True:
		if p.next == None:
			break
		if p.next.data < store.data:
			p = p.next
		else:
			temp = p.next
			p.next = store
			store = temp
			p = p.next
		if p.next == None:
			break
	p.next = store
	return end

def mergesortt(arr, l, r):
	if l < r:
		m = (l + r) // 2
		head1 = mergesortt(arr, l, m)
		head2 = mergesortt(arr, m + 1, r)
		head123 = sortedMerge(head1, head2)
		return head123
	else:
		return arr[l]

class Solution:

	def mergeSort(self, head):
		arr = []
		temp = head
		r = 0
		while temp != None:
			arr.append(temp)
			nextt = temp.next
			temp.next = None
			temp = nextt
			r += 1
		headd = mergesortt(arr, 0, r - 1)
		return headd


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

def mergesort(head):
	if head:
		if not head.next:
			return head
		slow = fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		nxt = slow.next
		slow.next = None
		l = mergesort(head)
		r = mergesort(nxt)
		head = merge(l, r)
		return head
	return None

class Solution:

	def mergeSort(self, head):
		return mergesort(head)


class Solution:

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		slow = head
		fast = head
		prev = None
		while fast and fast.next:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		prev.next = None
		ll1 = head
		ll2 = slow
		ll1 = self.mergeSort(ll1)
		ll2 = self.mergeSort(ll2)
		flag = Node(None)
		head = flag
		while ll1 and ll2:
			if ll1.data <= ll2.data:
				head.next = ll1
				head = head.next
				ll1 = ll1.next
				head.next = None
			else:
				head.next = ll2
				head = head.next
				ll2 = ll2.next
				head.next = None
		if ll1:
			head.next = ll1
		elif ll2:
			head.next = ll2
		return flag.next


class Solution:

	def mergeSort(self, head):

		def findmid(node):
			(slow, fast) = (node, node)
			while fast.next and fast.next.next:
				slow = slow.next
				fast = fast.next.next
			return slow

		def merge(start):
			if not start or not start.next:
				return start
			middle = findmid(start)
			mid = middle.next
			middle.next = None
			left = merge(start)
			right = merge(mid)
			result = mergelists(left, right)
			return result

		def mergelists(left, right):
			res = Node(0)
			dummy = res
			if not left:
				return right
			if not right:
				return left
			while left and right:
				if left.data <= right.data:
					res.next = left
					left = left.next
				else:
					res.next = right
					right = right.next
				res = res.next
			if left:
				res.next = left
			if right:
				res.next = right
			return dummy.next
		return merge(head)


class Solution:

	def merge(self, head1, head2):
		newhead = Node(None)
		t = newhead
		t1 = head1
		t2 = head2
		while t1 is not None and t2 is not None:
			if t1.data < t2.data:
				t.next = t1
				t1 = t1.next
				t = t.next
			else:
				t.next = t2
				t2 = t2.next
				t = t.next
		while t1 is not None:
			t.next = t1
			t1 = t1.next
			t = t.next
		while t2 is not None:
			t.next = t2
			t2 = t2.next
			t = t.next
		return newhead.next

	def getMid(self, head):
		s = head
		f = head
		p = None
		while f is not None and f.next is not None:
			p = s
			s = s.next
			f = f.next.next
		return s if f is not None else p

	def mergeSort(self, head):
		head = self.merge_sort(head)
		return head

	def merge_sort(self, head):
		if head is None or head.next is None:
			return head
		else:
			mid = self.getMid(head)
			midNext = mid.next
			mid.next = None
			head1 = self.merge_sort(head)
			head2 = self.merge_sort(midNext)
			newHead = self.merge(head1, head2)
			return newHead


class Solution:

	def merge(self, left, right):
		dummy = Node(-1)
		curr = dummy
		while left != None and right != None:
			if left.data < right.data:
				curr.next = left
				curr = left
				left = left.next
			else:
				curr.next = right
				curr = right
				right = right.next
		if left == None:
			curr.next = right
		if right == None:
			curr.next = left
		return dummy.next

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		left = head
		slow = head
		fast = head.next
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		mid = slow
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		ans = self.merge(left, right)
		return ans


class Solution:

	def get_mid(self, head):
		(slow, fast) = (head, head.next)
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

	def merge(self, head1, head2):
		if head1 == None and head2 == None:
			return head1
		elif head1 == None and head2 != None:
			return head2
		elif head1 != None and head2 == None:
			return head1
		new_head = None
		(itr1, itr2) = (head1, head2)
		if head1.data < head2.data:
			new_head = head1
			itr1 = itr1.next
		else:
			new_head = head2
			itr2 = itr2.next
		temp = new_head
		while itr1 and itr2:
			if itr1.data < itr2.data:
				temp.next = itr1
				itr1 = itr1.next
			else:
				temp.next = itr2
				itr2 = itr2.next
			temp = temp.next
		while itr1:
			temp.next = itr1
			itr1 = itr1.next
			temp = temp.next
		while itr2:
			temp.next = itr2
			itr2 = itr2.next
			temp = temp.next
		return new_head

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		left = head
		temp = self.get_mid(head)
		right = temp.next
		temp.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		head = self.merge(left, right)
		return head


class Solution:

	def merge(self, head1, head2):
		if head1 == None:
			return head2
		elif head2 == None:
			return head1
		temp = Node(-1)
		top = temp
		while head1 != None and head2 != None:
			if head1.data < head2.data:
				temp.next = head1
				head1 = head1.next
			else:
				temp.next = head2
				head2 = head2.next
			temp = temp.next
		if head1 != None:
			temp.next = head1
		if head2 != None:
			temp.next = head2
		return top.next

	def getMid(self, head):
		fast = head
		slow = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		mid = self.getMid(head)
		right = mid
		mid = mid.next
		right.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(mid)
		return self.merge(left, right)


class Solution:

	def midOfList(self, head):
		if head is None:
			return
		slow = fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		return slow

	def mergeSortedList(self, left, right):
		if not left:
			return right
		if not right:
			return left
		dummy = Node(-1)
		temp = dummy
		while left and right:
			if left.data >= right.data:
				temp.next = right
				right = right.next
				temp = temp.next
			else:
				temp.next = left
				left = left.next
				temp = temp.next
		if left:
			temp.next = left
		if right:
			temp.next = right
		return dummy.next

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		mid = self.midOfList(head)
		nextMid = mid.next
		mid.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(nextMid)
		res = self.mergeSortedList(left, right)
		return res


class Solution:

	def mergeSort(self, head):

		def midd(head):
			(slow, fast) = (head, head.next)
			while fast and fast.next:
				slow = slow.next
				fast = fast.next.next
			return slow

		def merge(head1, head2):
			dummy = Node(-1)
			dummy_tail = dummy
			curr1 = head1
			curr2 = head2
			while curr1 and curr2:
				if curr1.data < curr2.data:
					dummy_tail.next = curr1
					dummy_tail = curr1
					curr1 = curr1.next
				else:
					dummy_tail.next = curr2
					dummy_tail = curr2
					curr2 = curr2.next
			if curr1:
				dummy_tail.next = curr1
			if curr2:
				dummy_tail.next = curr2
			return dummy.next

		def merge_sort(head):
			if head is None or head.next is None:
				return head
			mid = midd(head)
			left = head
			right = mid.next
			mid.next = None
			left = merge_sort(left)
			right = merge_sort(right)
			res = merge(left, right)
			return res
		return merge_sort(head)


class Solution:

	def mergeSort(self, head):
		lst = []
		while head:
			lst.append(head.data)
			head = head.next
		lst.sort()
		a = Node(0)
		tmp = a
		for i in lst:
			tmp.next = Node(i)
			tmp = tmp.next
		return a.next


class Solution:

	def mergeSort(self, head):
		if not head or not head.next:
			return head
		(slow, fast, prev) = (head, head, head)
		while fast and fast.next:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		mid = slow
		prev.next = None
		head1 = self.mergeSort(head)
		head2 = self.mergeSort(mid)
		merged_list = self.merge(head1, head2)
		return merged_list

	def merge(self, head1, head2):
		dummy = Node(0)
		temp = dummy
		while head1 and head2:
			if head1.data <= head2.data:
				temp.next = head1
				temp = temp.next
				head1 = head1.next
			else:
				temp.next = head2
				temp = temp.next
				head2 = head2.next
		if head1:
			temp.next = head1
		if head2:
			temp.next = head2
		return dummy.next


class Solution:

	def getMid(self, head):
		s = head
		f = head.next
		while f and f.next:
			s = s.next
			f = f.next.next
		return s

	def merge(self, left, right):
		head = Node(-1)
		tail = head
		while left and right:
			if left.data < right.data:
				tail.next = Node(left.data)
				left = left.next
			elif left.data >= right.data:
				tail.next = Node(right.data)
				right = right.next
			tail = tail.next
			if left is None:
				tail.next = right
			if right is None:
				tail.next = left
		return head.next

	def mergeSort(self, head):
		if not head or not head.next:
			return head
		mid = self.getMid(head)
		left = head
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		result = self.merge(left, right)
		return result


class Solution:

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		temp = head
		(slow, fast) = (head, head)
		while fast and fast.next:
			temp = slow
			slow = slow.next
			fast = fast.next.next
		mid = slow
		temp.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(mid)
		return self.merge(left, right)

	def merge(self, left, right):
		dummy = Node(0)
		tail = dummy
		while left and right:
			if left.data <= right.data:
				tail.next = left
				left = left.next
			else:
				tail.next = right
				right = right.next
			tail = tail.next
		if left:
			tail.next = left
		if right:
			tail.next = right
		return dummy.next


class Solution:

	def merge(self, head1, head2):
		head = Node(-1)
		tmp = head
		while head1 != None and head2 != None:
			if head1.data <= head2.data:
				tmp.next = Node(head1.data)
				head1 = head1.next
			else:
				tmp.next = Node(head2.data)
				head2 = head2.next
			tmp = tmp.next
		while head1 != None:
			tmp.next = Node(head1.data)
			head1 = head1.next
			tmp = tmp.next
		while head2 != None:
			tmp.next = Node(head2.data)
			head2 = head2.next
			tmp = tmp.next
		return head.next

	def get_middle(self, head):
		slow = head
		fast = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		mid = self.get_middle(head)
		nxt_to_middle = mid.next
		mid.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(nxt_to_middle)
		sorted_list = self.merge(left, right)
		return sorted_list


class Solution:

	def merge(self, head1, head2):
		merged = Node(-1)
		temp = merged
		while head1 != None and head2 != None:
			if head1.data < head2.data:
				temp.next = head1
				head1 = head1.next
			else:
				temp.next = head2
				head2 = head2.next
			temp = temp.next
		while head1 != None:
			temp.next = head1
			head1 = head1.next
			temp = temp.next
		while head2 != None:
			temp.next = head2
			head2 = head2.next
			temp = temp.next
		return merged.next

	def get_middle_element(self, head):
		slow = head
		fast = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

	def mergeSort(self, head):
		if head.next == None:
			return head
		mid = self.get_middle_element(head)
		head2 = mid.next
		mid.next = None
		newHead1 = self.mergeSort(head)
		newHead2 = self.mergeSort(head2)
		finalHead = self.merge(newHead1, newHead2)
		return finalHead


class Solution:

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head

		def findmid(node):
			s = node
			f = node.next
			while f != None and f.next != None:
				s = s.next
				f = f.next.next
			return s

		def merge(le, ri):
			ans = Node(None)
			tmp = ans
			while le != None and ri != None:
				if le.data < ri.data:
					tmp.next = le
					tmp = le
					le = le.next
				else:
					tmp.next = ri
					tmp = ri
					ri = ri.next
			while le != None:
				tmp.next = le
				tmp = le
				le = le.next
			while ri != None:
				tmp.next = ri
				tmp = ri
				ri = ri.next
			ans = ans.next
			return ans
		mid = findmid(head)
		left = head
		right = mid.next
		mid.next = None
		leftsort = self.mergeSort(left)
		rightsort = self.mergeSort(right)
		res = merge(leftsort, rightsort)
		return res


class Solution:

	def findMid(self, head):
		if not head or not head.next:
			return head
		slow = head
		fast = head
		while fast and fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		return slow

	def sort(self, head, count):
		if head.next == None:
			return head
		else:
			mid = self.findMid(head)
			l = head
			l2 = mid.next
			mid.next = None
			l = self.sort(l, count + 1)
			l2 = self.sort(l2, count + 1)
			dummy = Node(-1)
			curr = dummy
			while l and l2:
				if l.data <= l2.data:
					curr.next = l
					l = l.next
					curr = curr.next
				else:
					curr.next = l2
					l2 = l2.next
					curr = curr.next
			while l:
				curr.next = l
				l = l.next
				curr = curr.next
			while l2:
				curr.next = l2
				l2 = l2.next
				curr = curr.next
			curr.next = None
			return dummy.next

	def mergeSort(self, head):
		head = self.sort(head, 0)
		return head


class Node:

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

class Solution:

	def mergeSort(self, head):
		l = []
		a = head
		while a is not None:
			l += [a.data]
			a = a.next
		l = sorted(l)
		head = None
		head = Node(l[0])
		n = head
		for i in range(1, len(l)):
			no = Node(l[i])
			no.next = None
			n.next = no
			n = n.next
		return head


class Solution:

	def get_middle(self, head):
		if head == None or head.next == None:
			return head
		(f, s) = (head, head)
		while f.next != None and f.next.next != None:
			(s, f) = (s.next, f.next.next)
		return s

	def merge_list(self, head1, head2):
		v = 0
		if head1 is None and head2 is None:
			return None
		elif head1 is None:
			v = head2.data - 1
		elif head2 is None:
			v = head1.data - 1
		else:
			v = min(head1.data, head2.data) - 1
		head = Node(v)
		c = head
		while head1 != None and head2 != None:
			if head1.data < head2.data:
				c.next = head1
				head1 = head1.next
			else:
				c.next = head2
				head2 = head2.next
			c = c.next
		if head1 != None:
			c.next = head1
		else:
			c.next = head2
		return head.next

	def print_list(self, head):
		p = head
		while p is not None:
			print(p.data, end='-> ')
			p = p.next
		print('')

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		mid = self.get_middle(head)
		t = mid.next
		mid.next = None
		after_mid = self.mergeSort(t)
		before_mid = self.mergeSort(head)
		merged = self.merge_list(before_mid, after_mid)
		return merged


class Solution:

	def mergeSort(self, head):
		s = head
		ll = []
		while s:
			ll.append(s.data)
			s = s.next
		ll.sort()
		s = head
		while s:
			s.data = ll.pop(0)
			s = s.next
		return head


class Solution:

	def mergeSort(self, head):
		a = []
		t = head
		while t != None:
			a.append(t.data)
			t = t.next
		a.sort()
		t = head
		i = 0
		while t != None:
			t.data = a[i]
			i += 1
			t = t.next
		return head


class Solution:

	def findMiddle(self, head):
		if head == None or head.next == None:
			return head
		tur = head
		hare = head
		while hare and hare.next and hare.next.next:
			tur = tur.next
			hare = hare.next.next
		return tur

	def merge(self, h1, h2):
		dum = Node(-1)
		curr = dum
		while h1 and h2:
			if h1.data <= h2.data:
				curr.next = h1
				h1 = h1.next
			else:
				curr.next = h2
				h2 = h2.next
			curr = curr.next
		while h1:
			curr.next = h1
			h1 = h1.next
			curr = curr.next
		while h2:
			curr.next = h2
			h2 = h2.next
			curr = curr.next
		return dum.next

	def solveSort(self, head):
		if head == None or head.next == None:
			return head
		middle = self.findMiddle(head)
		nxt = middle.next
		middle.next = None
		l = self.solveSort(head)
		r = self.solveSort(nxt)
		return self.merge(l, r)

	def mergeSort(self, head):
		return self.solveSort(head)


class Solution:

	def mer(self, arr, mid, l, r):
		n1 = mid - l + 1
		n2 = r - mid
		left = []
		right = []
		for i in range(n1):
			left.append(arr[l + i])
		for i in range(n2):
			right.append(arr[mid + 1 + i])
		i = 0
		j = 0
		k = l
		while i < n1 and j < n2:
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
				j += 1
			k += 1
		while i < n1:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = right[j]
			j += 1
			k += 1

	def merge(self, arr, l, r):
		if l < r:
			mid = (l + r) // 2
			self.merge(arr, l, mid)
			self.merge(arr, mid + 1, r)
			self.mer(arr, mid, l, r)

	def mergeSort(self, head):
		li = []
		temp = head
		while temp:
			li.append(temp.data)
			temp = temp.next
		self.merge(li, 0, len(li) - 1)
		l3 = LinkedList()
		for i in li:
			l3.append(i)
		return l3.head


class Solution:

	def findmid(self, head):
		slow = head
		fast = head.next
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

	def merge(self, head1, head2):
		if head1 == None and head2 == None:
			return None
		else:
			temp = dum = Node(0)
			lo = head1
			hi = head2
			while lo and hi:
				if lo.data <= hi.data:
					dum.next = lo
					lo = lo.next
				elif lo.data > hi.data:
					dum.next = hi
					hi = hi.next
				dum = dum.next
			if lo:
				dum.next = lo
			if hi:
				dum.next = hi
			return temp.next

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		left = head
		mid = self.findmid(left)
		right = mid.next
		mid.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		return self.merge(left, right)


class Solution:

	def mergeSort(self, head):
		if not head or not head.next:
			return head
		left = head
		mid = self.getMid(head)
		right = mid.next
		mid.next = None
		l = self.mergeSort(left)
		r = self.mergeSort(right)
		return self.merge(l, r)

	def getMid(self, head):
		(slow, fast) = (head, head.next)
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		return slow

	def merge(self, l, r):
		dummy = Node(0)
		tail = dummy
		while l and r:
			if l.data <= r.data:
				tail.next = l
				l = l.next
			else:
				tail.next = r
				r = r.next
			tail = tail.next
		if l:
			tail.next = l
		if r:
			tail.next = r
		return dummy.next


class Solution:

	def mergeSort(self, head):
		if not head:
			return head
		if not head.next:
			return head
		slow = head
		fast = head
		while fast and fast.next and fast.next.next:
			fast = fast.next.next
			slow = slow.next
		temp = slow.next
		slow.next = None
		l = self.mergeSort(head)
		r = self.mergeSort(temp)
		return self.merge(l, r)

	def merge(self, l1, l2):
		if not l1:
			return l2
		elif not l2:
			return l1
		if l1.data <= l2.data:
			l1.next = self.merge(l1.next, l2)
			return l1
		else:
			l2.next = self.merge(l1, l2.next)
			return l2


import math

def getMiddle(head):
	if head is None:
		return head
	slow = head
	fast = head
	while fast.next is not None and fast.next.next is not None:
		slow = slow.next
		fast = fast.next.next
	return slow

def merge(left, right):
	result = None
	if left is None:
		return right
	if right is None:
		return left
	if left.data <= right.data:
		result = left
		result.next = merge(left.next, right)
	else:
		result = right
		result.next = merge(left, right.next)
	return result

class Solution:

	def mergeSort(self, head):
		S = Solution()
		if head is None or head.next is None:
			return head
		slow = getMiddle(head)
		mid = slow.next
		slow.next = None
		left = S.mergeSort(head)
		right = S.mergeSort(mid)
		output = merge(left, right)
		return output


class Solution:

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		count = 0
		temp = head
		while temp:
			count += 1
			temp = temp.next
		current = head
		arr = []
		for i in range(count):
			arr.append(current.data)
			current = current.next
		arr.sort()
		head1 = None
		tail = None
		for i in range(count):
			node = Node(arr[i])
			if head1 == None:
				head1 = node
				tail = node
			else:
				tail.next = node
				tail = node
		return head1


class Solution:

	def findMid(self, head):
		slow = head
		fast = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow

	def merge(self, l, r):
		if l == None:
			return r
		if r == None:
			return l
		dummy = Node(-1)
		temp = dummy
		while l != None and r != None:
			if l.data < r.data:
				temp.next = l
				l = l.next
			else:
				temp.next = r
				r = r.next
			temp = temp.next
		while l != None:
			temp.next = l
			temp = temp.next
			l = l.next
		while r != None:
			temp.next = r
			temp = temp.next
			r = r.next
		return dummy.next

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		middle = self.findMid(head)
		left = head
		right = middle.next
		middle.next = None
		left = self.mergeSort(left)
		right = self.mergeSort(right)
		res = self.merge(left, right)
		return res


class Solution:

	def mergeSort(self, head):
		l = []
		while head:
			l.append(head.data)
			head = head.next
		l.sort()
		for i in l:
			print(i, end=' ')


class Solution:

	def mergeSort(self, head):
		if head is None:
			return None
		if head.next is None:
			return head
		split_linked_list_heads = self.split_give_two_linked_list(head)
		left_sorted_linked_list = self.mergeSort(split_linked_list_heads[0])
		right_sorted_linked_list = self.mergeSort(split_linked_list_heads[1])
		return self.merge_sorted_linked_list(left_sorted_linked_list, right_sorted_linked_list)

	def merge_sorted_linked_list(self, head_1, head_2):
		if head_1.data <= head_2.data:
			new_head = Node(head_1.data)
			curr_head_1 = head_1.next
			curr_head_2 = head_2
		else:
			new_head = Node(head_2.data)
			curr_head_1 = head_1
			curr_head_2 = head_2.next
		curr = new_head
		while curr_head_1 is not None or curr_head_2 is not None:
			if curr_head_1 is None:
				curr.next = Node(curr_head_2.data)
				curr_head_2 = curr_head_2.next
			elif curr_head_2 is None:
				curr.next = Node(curr_head_1.data)
				curr_head_1 = curr_head_1.next
			elif curr_head_1.data <= curr_head_2.data:
				curr.next = Node(curr_head_1.data)
				curr_head_1 = curr_head_1.next
			else:
				curr.next = Node(curr_head_2.data)
				curr_head_2 = curr_head_2.next
			curr = curr.next
		return new_head

	def get_count(self, head):
		count = 0
		curr = head
		while curr is not None:
			count = count + 1
			curr = curr.next
		return count

	def split_give_two_linked_list(self, head):
		count = self.get_count(head)
		if count % 2 == 0:
			half_count = count // 2 - 1
		else:
			half_count = count // 2
		curr = head
		while half_count > 0:
			curr = curr.next
			half_count = half_count - 1
		if curr is not None:
			new_head = curr.next
			curr.next = None
		else:
			new_head = None
		return [head, new_head]


class Solution:

	def mergeSort(self, head):
		l = []
		while head:
			l.append(head.data)
			head = head.next
		l.sort()
		cur = dummy = Node(0)
		for e in l:
			cur.next = Node(e)
			cur = cur.next
		return dummy.next


class Solution:

	def mergeSort(self, head):
		arr = []
		while head:
			arr.append(head.data)
			head = head.next
		temp = new = Node(0)
		for i in sorted(arr):
			temp.next = Node(i)
			temp = temp.next
		return new.next


class Solution:

	def mergeSort(self, head):
		temp = head
		l = []
		while temp != None:
			l.append(temp.data)
			temp = temp.next
		l.sort()
		head = temp = None
		for i in l:
			n = Node(i)
			if head == None:
				head = temp = n
			else:
				temp.next = n
				temp = n
		return head


class Solution:

	def getSize(self, head):
		count = 0
		curr_node = head
		while curr_node:
			count += 1
			curr_node = curr_node.next
		return count

	def splitList(self, source):
		if source == None or source.next == None:
			frontRef = source
			backRef = None
		else:
			size = self.getSize(source)
			length = (size + 1) // 2
			frontRef = source
			while length > 1:
				length -= 1
				frontRef = frontRef.next
			backRef = frontRef.next
			frontRef.next = None
		return [source, backRef]

	def mergeList(self, head_a, head_b):
		result = LinkedList()
		if head_a == None:
			return head_b
		if head_b == None:
			return head_a
		if head_a.data <= head_b.data:
			result.head = head_a
			result.head.next = self.mergeList(head_a.next, head_b)
		else:
			result.head = head_b
			result.head.next = self.mergeList(head_a, head_b.next)
		return result.head

	def mergeSort(self, head):
		a = LinkedList()
		b = LinkedList()
		if head == None or head.next == None:
			return head
		node_list = self.splitList(head)
		a.head = node_list[0]
		b.head = node_list[1]
		a.head = self.mergeSort(a.head)
		b.head = self.mergeSort(b.head)
		return self.mergeList(a.head, b.head)


class Solution:

	def mergeSort(self, head):
		list1 = []
		t1 = head
		while t1:
			list1.append(t1.data)
			t1 = t1.next
		list1.sort()
		temp = head
		i = 0
		while temp != None:
			temp.data = list1[i]
			i += 1
			temp = temp.next
		return head


class Solution:

	def getMiddleElements(self, head):
		if head is None:
			return head
		tortoise = head
		rabbit = head
		while rabbit.next is not None and rabbit.next.next is not None:
			tortoise = tortoise.next
			rabbit = rabbit.next.next
		return tortoise

	def sortedMerge(self, head1, head2):
		if head1 is None:
			return head2
		if head2 is None:
			return head1
		if head1.data < head2.data:
			mergedResult = head1
			mergedResult.next = self.sortedMerge(head1.next, head2)
		else:
			mergedResult = head2
			mergedResult.next = self.sortedMerge(head1, head2.next)
		return mergedResult

	def mergeSort(self, head):
		if head is None or head.next is None:
			return head
		middleElement = self.getMiddleElements(head)
		nextToMiddle = middleElement.next
		middleElement.next = None
		leftSplit = self.mergeSort(head)
		rightSplit = self.mergeSort(nextToMiddle)
		SortedmergedList = self.sortedMerge(leftSplit, rightSplit)
		return SortedmergedList


class Solution:

	def merging(self, a, b):
		if a == None:
			return b
		if b == None:
			return a
		result = None
		if a.data > b.data:
			result = b
			result.next = self.merging(a, b.next)
		else:
			result = a
			result.next = self.merging(a.next, b)
		return result

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		middle = self.middleOne(head)
		second = middle.next
		middle.next = None
		left = self.mergeSort(head)
		right = self.mergeSort(second)
		new = self.merging(left, right)
		return new

	def middleOne(self, head):
		fast = head
		slow = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow


class Solution:

	def mergeSort(self, head):
		tmp = []
		curr = prev = head
		while curr:
			tmp.append(curr.data)
			curr = curr.next
		tmp.sort()
		i = 0
		while prev:
			prev.data = tmp[i]
			i = i + 1
			prev = prev.next
		return head


class Solution:

	def mergee(self, arr, mid, l, r):
		n1 = mid - l + 1
		n2 = r - mid
		left = []
		right = []
		for i in range(n1):
			left.append(arr[l + i])
		for i in range(n2):
			right.append(arr[mid + 1 + i])
		i = 0
		j = 0
		k = l
		while i < n1 and j < n2:
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
				j += 1
			k += 1
		while i < n1:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = right[j]
			j += 1
			k += 1

	def merge(self, arr, l, r):
		if l < r:
			mid = (l + r) // 2
			self.merge(arr, l, mid)
			self.merge(arr, mid + 1, r)
			self.mergee(arr, mid, l, r)

	def mergeSort(self, head):
		p = head
		l = []
		while p:
			l.append(p.data)
			p = p.next
		self.merge(l, 0, len(l) - 1)
		l3 = Node(-1)
		c = l3
		for i in l:
			c.next = Node(i)
			c = c.next
		return l3.next


class Solution:

	def mergeSort(self, head):
		b = []
		tmp = head
		while tmp:
			b.append(tmp.data)
			tmp = tmp.next
		tmp = head
		b.sort()
		for i in b:
			tmp.data = i
			tmp = tmp.next
		return head


def middle(head):
	if head.next.next == None:
		return head
		return head
	(slow, fast) = (head, head)
	while fast and fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	return slow

def merge(l, r):
	(result, tresult) = (None, None)
	while l or r:
		if l == None:
			if tresult == None:
				return r
			else:
				result.next = r
				return tresult
		elif r == None:
			if tresult == None:
				return l
			else:
				result.next = l
				return tresult
		elif l.data >= r.data:
			if result is None:
				result = r
				tresult = result
			else:
				result.next = r
				result = result.next
			r = r.next
		else:
			if result is None:
				result = l
				tresult = result
			else:
				result.next = l
				result = result.next
			l = l.next
	result.next = None
	return tresult

class Solution:

	def mergeSort(self, head):
		if head == None or head.next == None:
			return head
		mid = middle(head)
		temp = mid.next
		mid_next = temp
		mid.next = None
		l = self.mergeSort(head)
		r = self.mergeSort(mid_next)
		return merge(l, r)