Given a Linked list of size N, the list is in alternating ascending and descending orders. Sort the given linked list in non-decreasing order.
 
Example 1:
Input:
LinkedList: 1->9->2->8->3->7
Output: 1 2 3 7 8 9
Explanation: After sorting the given
list will be 1-> 2-> 3-> 7-> 8-> 9.
 
Example 2:
Input:
LinkedList: 13->99->21->80->50
Output: 13 21 50 80 99
Explanation: After sorting the given list 
will be 13-> 21-> 50-> 80-> 99.
 
Your Task:
You do not need to read input or print anything. The task is to complete the function sort() which should sort the linked list in non-decreasing order. 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= Number of nodes <= 100
0 <= Values of the linked list <= 10^{3}

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

'''
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
'''
def sort(h1):
    #return head


Solutions:
def sort(h1):
	l = []
	temp1 = h1
	while temp1:
		l.append(temp1.data)
		temp1 = temp1.next
	j = 0
	l.sort()
	temp = h1
	while temp:
		temp.data = l[j]
		j += 1
		temp = temp.next
	return h1


def sort(h1):
	temp = h1
	l = []
	while temp != None:
		l.append(temp.data)
		temp = temp.next
	l = sorted(l)
	dummy = Node(-1)
	p = dummy
	k = 0
	while k < len(l):
		dummy.next = Node(l[k])
		dummy = dummy.next
		k += 1
	return p.next


def sort(h1):
	a = []
	temp = h1
	while temp != None:
		a.append(temp.data)
		temp = temp.next
	j = 0
	a.sort()
	temp1 = h1
	while temp1:
		temp1.data = a[j]
		j += 1
		temp1 = temp1.next
	return h1


def sort(h1):
	l = []
	a = h1
	while a:
		l.append(a.data)
		a = a.next
	j = 0
	l.sort()
	b = h1
	while b:
		b.data = l[j]
		j += 1
		b = b.next
	return h1


def sort(h1):
	l = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	l.sort()
	head = Node(l[0])
	t = head
	i = 1
	while i < len(l):
		t.next = Node(l[i])
		t = t.next
		i += 1
	return head


def sort(h1):
	array = []
	newnode = h1
	result = newnode
	while h1:
		array.append(h1.data)
		h1 = h1.next
	array = sorted(array)
	for num in array:
		newnode.data = num
		newnode = newnode.next
	return result


def sort(h1):
	a = []
	cur = h1
	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


def sort(h1):
	x = []
	while h1:
		x.append(h1.data)
		h1 = h1.next
	x.sort()
	head = Node(x[0])
	cur = head
	for i in range(1, len(x)):
		cur.next = Node(x[i])
		cur = cur.next
	return head


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


def sort(h1):
	fast = h1
	l1 = []
	while fast is not None:
		l1.append(fast.data)
		fast = fast.next
	fast = h1
	l1.sort()
	for i in l1:
		fast.data = i
		fast = fast.next
	return h1


def mergetwolist(l1, l2):
	start = Node(0)
	curr = start
	while l1 is not None and l2 is not None:
		if l1.data < l2.data:
			curr.next = l1
			curr = l1
			l1 = l1.next
		else:
			curr.next = l2
			curr = l2
			l2 = l2.next
	if l1 is None:
		l1 = l2
	curr.next = l1
	return start.next

def sort(curr):
	sorted_start = Node(0)
	curr_sorted = sorted_start
	sorted_end = None
	odd = True
	while curr is not None:
		if odd:
			curr_sorted.next = curr
			curr_sorted = curr
			curr = curr.next
		else:
			node = curr.next
			curr.next = sorted_end
			sorted_end = curr
			curr = node
		odd = not odd
	curr_sorted.next = None
	return mergetwolist(sorted_start.next, sorted_end)


def sort(head):
	if not head or not head.next:
		return head
	(l1, l2) = (head, head.next)
	(ptr1, ptr2) = (l1, l2)
	while ptr1 and ptr2:
		ptr1.next = ptr2.next
		ptr1 = ptr1.next
		ptr2.next = ptr1.next if ptr1 else None
		ptr2 = ptr2.next
	(prev, cur, nxt) = (None, l2, l2.next)
	while cur:
		cur.next = prev
		prev = cur
		cur = nxt
		nxt = cur.next if cur else None
	l2 = prev
	start = Node(0)
	ptr = start
	while l1 and l2:
		if l1.data < l2.data:
			ptr.next = l1
			l1 = l1.next
		else:
			ptr.next = l2
			l2 = l2.next
		ptr = ptr.next
		ptr.next = None
	ptr.next = l1 if l1 else l2
	return start.next


def sort(h1):
	l = []
	cur = h1
	i = 0
	while cur:
		l.append(cur.data)
		cur = cur.next
	l.sort()
	cur = h1
	while cur:
		cur.data = l[i]
		i += 1
		cur = cur.next
	return h1


def sort(h1):
	s1 = []
	while h1:
		s1.append(h1.data)
		h1 = h1.next
	ll = Llist()
	tail = None
	for e in sorted(s1):
		tail = ll.insert(e, tail)
	return ll.head


def sort(head):
	l = 0
	a = head
	while a != None:
		l += 1
		a = a.next
	g = head
	a = head.next
	prev = head
	if head.next != None:
		front = head.next.next
	left_count = 0
	while a != None:
		temp = Node(a.data)
		temp.next = head
		head = temp
		if prev != None:
			prev.next = front
		prev = front
		if a.next != None:
			a = a.next.next
		else:
			a = None
		if front != None and front.next != None:
			front = front.next.next
		left_count += 1
	p = head
	right_count = l - left_count
	rc = 0
	lc = 0
	temp = Node(0)
	ptr = temp
	while lc < left_count and rc < right_count:
		if g.data < p.data:
			t = Node(g.data)
			temp.next = t
			temp = t
			rc += 1
			g = g.next
		else:
			t = Node(p.data)
			temp.next = t
			temp = t
			lc += 1
			p = p.next
	while lc < left_count:
		t = Node(p.data)
		temp.next = t
		temp = t
		lc += 1
		p = p.next
	while rc < right_count:
		t = Node(g.data)
		temp.next = t
		temp = t
		rc += 1
		g = g.next
	return ptr.next


def sort(h1):
	temp = h1
	arr = []
	while temp:
		arr.append(temp.data)
		temp = temp.next
	arr.sort()
	temp = h1
	i = 0
	while temp:
		temp.data = arr[i]
		i += 1
		temp = temp.next
	return h1


def reverse(head):
	if head is None or head.next is None:
		return head
	pre = None
	cur = head
	while cur is not None:
		t = cur.next
		cur.next = pre
		pre = cur
		cur = t
	return pre

def sort(head):
	if head is None or head.next is None:
		return head
	ne = head.next
	ei = head
	oi = ne
	while ei.next is not None and oi.next is not None:
		if ei.next.next is not None:
			ei.next = ei.next.next
			ei = ei.next
		if oi.next.next is not None:
			oi.next = oi.next.next
			oi = oi.next
	oi.next = None
	ei.next = None
	t = reverse(ne)
	c1 = head
	c2 = t
	main = None
	cm = main
	while c1 is not None and c2 is not None:
		if c2.data <= c1.data:
			if main is None:
				main = c2
				c2 = c2.next
				cm = main
			else:
				cm.next = c2
				c2 = c2.next
				cm = cm.next
		elif main is None:
			main = c1
			c1 = c1.next
			cm = main
		else:
			cm.next = c1
			c1 = c1.next
			cm = cm.next
	if c1 is not None:
		if main is not None:
			cm.next = c1
		else:
			main = c1
	if c2 is not None:
		if main is not None:
			cm.next = c2
		else:
			main = c2
	return main


def sort(h1):
	arr = []
	temp = h1
	while temp:
		arr.append(temp.data)
		temp = temp.next
	arr.sort()
	n = Node(arr[0])
	temp1 = h1
	head = n
	i = 1
	while i < len(arr):
		curr_node = Node(arr[i])
		n.next = curr_node
		n = n.next
		i += 1
	return head


def sort(h1):
	s = []
	temp = h1
	while temp:
		s.append(temp.data)
		temp = temp.next
	j = 0
	s.sort()
	temp = h1
	while temp:
		temp.data = s[j]
		j += 1
		temp = temp.next
	return h1


def sort(h1):
	l = []
	p = h1
	while p:
		l.append(p.data)
		p = p.next
	l.sort()
	n = len(l)
	p = h1
	i = 0
	while p:
		if i == 0:
			p.data = l[i]
			h1 = p
		else:
			p.data = l[i]
		p = p.next
		i = i + 1
	return h1


class Sort:

	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

	def mergeSort(self, h1):
		if h1 == None or h1.next == None:
			return h1
		mid = self.getMiddle(h1)
		t = mid.next
		mid.next = None
		left = self.mergeSort(h1)
		right = self.mergeSort(t)
		sortedlist = self.sortedMerge(left, right)
		return sortedlist

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

def sort(h1):
	obj = Sort()
	return obj.mergeSort(h1)


def sort(h1):
	li = []
	temp = h1
	while temp:
		li.append(temp.data)
		temp = temp.next
	i = 0
	li.sort()
	tem = h1
	while tem:
		tem.data = li[i]
		i += 1
		tem = tem.next
	return h1


def sort(h1):
	list = []
	head = h1
	temp = h1
	while head:
		list.append(head.data)
		head = head.next
	list.sort()
	i = 0
	while h1:
		h1.data = list[i]
		h1 = h1.next
		i += 1
	return temp


def sort(h1):
	rec = []
	while h1:
		rec.append(h1.data)
		h1 = h1.next
	rec.sort()
	hd = Node(rec[0])
	temp = hd
	for i in range(1, len(rec)):
		temp.next = Node(rec[i])
		temp = temp.next
	return hd


def sort(h1):
	l = []
	temp = h1
	if temp == None:
		return None
	while temp:
		l.append(temp.data)
		temp = temp.next
	temp = h1
	l.sort(reverse=True)
	while temp:
		temp.data = l.pop()
		temp = temp.next
	return h1


def sort(h1):
	n1 = h1
	n2 = n1.next
	while n2 != None or n1.next != None:
		if n1.data > n2.data:
			t = n1.data
			n1.data = n2.data
			n2.data = t
		n2 = n2.next
		if n2 == None:
			n1 = n1.next
			n2 = n1.next
	return h1


def sort(h1):
	l = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	ll = Llist()
	l.sort()
	tail = None
	for i in l:
		tail = ll.insert(i, tail)
	return ll.head


def sort(h1):
	while 1:
		swapped = False
		curr = h1
		while curr.next is not None:
			if curr.data > curr.next.data:
				(curr.data, curr.next.data) = (curr.next.data, curr.data)
				swapped = True
			curr = curr.next
		if swapped == False:
			break
	return h1


def sort(head):
	curr = head
	count = 0
	while curr:
		count += 1
		curr = curr.next
	for i in range(count):
		curr = head
		while curr and curr.next:
			if curr.data > curr.next.data:
				(curr.data, curr.next.data) = (curr.next.data, curr.data)
			curr = curr.next
	return head


def sort(h1):

	def merge(l1, l2):
		ans = Node(0)
		p = ans
		while l1 and l2:
			if l1.data >= l2.data:
				p.next = l2
				l2 = l2.next
			elif l1.data < l2.data:
				p.next = l1
				l1 = l1.next
			p = p.next
		if l1:
			p.next = l1
		if l2:
			p.next = l2
		return ans.next

	def reverseList(head):
		prev = None
		curr = head
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		return prev

	def splitList(head1, head2):
		p1 = head1
		p2 = head2
		temp = h1
		while temp:
			p1.next = temp
			p1 = p1.next
			temp = temp.next
			if temp:
				p2.next = temp
				p2 = p2.next
				temp = temp.next
		p1.next = None
		p2.next = None
	dummy1 = Node(0)
	dummy2 = Node(0)
	splitList(dummy1, dummy2)
	dummy1 = dummy1.next
	dummy2 = dummy2.next
	dummy2 = reverseList(dummy2)
	return merge(dummy1, dummy2)


def sort(h1):
	x = []
	while h1:
		x.append(h1.data)
		h1 = h1.next
	x.sort()
	for i in x:
		print(i, end=' ')


def sort(head):
	if not head or not head.next:
		return head

	def merge(l1, l2):
		ans = Node(0)
		p = ans
		while l1 and l2:
			if l1.data >= l2.data:
				p.next = l2
				l2 = l2.next
			elif l1.data < l2.data:
				p.next = l1
				l1 = l1.next
			p = p.next
		if l1:
			p.next = l1
		if l2:
			p.next = l2
		return ans.next
	s = head
	f = head.next
	while f and f.next:
		s = s.next
		f = f.next.next
	right = s.next
	s.next = None
	left = head
	left = sort(left)
	right = sort(right)
	return merge(left, right)


def sort(h1):
	n1 = h1
	n2 = h1.next
	while n2 != None and n1.next != None:
		if n1.data > n2.data:
			(n1.data, n2.data) = (n2.data, n1.data)
		n2 = n2.next
		if n2 == None:
			n1 = n1.next
			n2 = n1.next
	return h1


def sort(head):
	i = head
	while i:
		j = i.next
		while j:
			if i.data > j.data:
				(i.data, j.data) = (j.data, i.data)
			j = j.next
		i = i.next
	return head


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

def mergeList(left, right):
	head = dummy = Node(data=None)
	while left and right:
		if left.data < right.data:
			dummy.next = left
			left = left.next
		else:
			dummy.next = right
			right = right.next
		dummy = dummy.next
	while left:
		dummy.next = left
		left = left.next
		dummy = dummy.next
	while right:
		dummy.next = right
		right = right.next
		dummy = dummy.next
	return head.next

def sort(h1):
	if h1 == None or h1.next == None:
		return h1
	left = h1
	right = getMid(h1)
	temp = right.next
	right.next = None
	right = temp
	left = sort(h1=left)
	right = sort(h1=right)
	return mergeList(left, right)


def sort(head):
	if head == None or head.next == None:
		return head
	slow = head
	fast = head.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	mid = slow.next
	slow.next = None
	left = sort(head)
	right = sort(mid)
	dumm = Node(0)
	curr = dumm
	while left and right:
		if left.data < right.data:
			curr.next = left
			left = left.next
		else:
			curr.next = right
			right = right.next
		curr = curr.next
	curr.next = left or right
	return dumm.next


def sort(h1):
	arr = []
	n = h1
	while n is not None:
		arr.append(n.data)
		n = n.next
	for i in range(len(arr)):
		for i in range(len(arr) - 1):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	head = None
	tail = None
	for i in range(len(arr)):
		if head == None:
			head = Node(arr[i])
			tail = head
		else:
			tail.next = Node(arr[i])
			tail = tail.next
	return head


def sort(h1):
	curr = h1
	arr = []
	while curr:
		arr.append(curr.data)
		curr = curr.next
	arr.sort()
	curr = h1
	for i in arr:
		curr.data = i
		curr = curr.next
	return h1


def reverse(head):
	prev = None
	curr = head
	while curr:
		nxt = curr.next
		curr.next = prev
		prev = curr
		curr = nxt
	return prev

def findLast(head):
	temp = head
	while temp.next:
		temp = temp.next
	return temp

def sort(head):
	if head == None or head.next == None:
		return head
	asc = head
	desc = head.next
	a = head
	d = head.next
	while a != None and d != None:
		a.next = d.next
		a = a.next
		if a == None:
			break
		d.next = a.next
		d = d.next
	if a != None:
		a.next = None
	if d != None:
		d.next = None
	desc = reverse(desc)
	dummy = Node(0)
	temp = dummy
	while asc != None and desc != None:
		if asc.data <= desc.data:
			temp.next = asc
			asc = asc.next
		else:
			temp.next = desc
			desc = desc.next
		temp = temp.next
	temp.next = asc if asc != None else desc
	return dummy.next


def sort(head):
	start = head
	arr1 = []
	arr2 = []
	while head and head.next:
		arr1.append(head.data)
		arr2.append(head.next.data)
		head = head.next.next
	if head:
		arr1.append(head.data)
	if len(arr1) > 1 and arr1[1] < arr1[0]:
		arr1.reverse()
	if len(arr2) > 1 and arr2[1] < arr2[0]:
		arr2.reverse()
	sorted_arr = []
	while arr1 and arr2:
		if arr1[-1] > arr2[-1]:
			sorted_arr.append(arr1.pop())
		else:
			sorted_arr.append(arr2.pop())
	sorted_arr += arr1[::-1] + arr2[::-1]
	head = start
	while head:
		head.data = sorted_arr.pop()
		head = head.next
	return start


def sort(h1):
	list = []
	current = h1
	while current:
		list.append(current.data)
		current = current.next
	list.sort()
	current = h1
	i = 0
	while current:
		current.data = list[i]
		current = current.next
		i += 1
	return h1


def sort(head):
	if not head or not head.next:
		return head
	slow = head
	fast = head.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	mid = slow.next
	slow.next = None
	left = sort(head)
	right = sort(mid)
	dummy = Node(-1)
	temp = dummy
	while left and right:
		if left.data <= right.data:
			temp.next = left
			left = left.next
		else:
			temp.next = right
			right = right.next
		temp = temp.next
	if left:
		temp.next = left
	if right:
		temp.next = right
	return dummy.next


def sort(h1):
	t = h1
	l = []
	while t:
		l.append(t.data)
		t = t.next
	l.sort()
	l.reverse()
	h1 = Node(l[0])
	l.remove(l[0])
	for i in l:
		node = Node(i)
		node.next = h1
		h1 = node
	return h1


def sort(h1):
	new = []
	newnode = Node(0)
	temp = newnode
	tempnode = h1
	while tempnode:
		new.append(tempnode.data)
		tempnode = tempnode.next
	new.sort()
	for i in range(len(new)):
		one = Node(new[i])
		temp.next = one
		temp = one
	return newnode.next


def sort(h1):
	a = []
	b = h1
	while b:
		a.append(b.data)
		b = b.next
	a.sort()
	a1 = a2 = Node(a[0])
	for i in range(1, len(a)):
		a1.next = Node(a[i])
		a1 = a1.next
	return a2


def sort(h1):
	res = []
	head = h1
	while h1:
		res.append(h1.data)
		h1 = h1.next
	res.sort()
	h1 = head
	while h1:
		h1.data = res.pop(0)
		h1 = h1.next
	return head


def sort(h1):
	m = []
	temp = h1
	while temp:
		m.append(temp.data)
		temp = temp.next
	m = sorted(m)
	temp = h1
	for i in m:
		temp.data = i
		temp = temp.next
	return h1


def sort(h1):
	temp = h1
	a = []
	while temp:
		a.append(temp.data)
		temp = temp.next
	a.sort()
	temp = h1
	for i in a:
		temp.data = i
		temp = temp.next
	return h1


def sort(h1):
	new_node = Node(0)
	x = []
	curr1 = h1
	tmp_node = new_node
	while curr1:
		x.append(curr1.data)
		curr1 = curr1.next
	for node in sorted(x):
		tmp_node.next = Node(node)
		tmp_node = tmp_node.next
	return new_node.next


def sort(h1):
	temp1 = h1
	temp2 = h1.next
	while temp2 != None or temp1.next != None:
		if temp1.data > temp2.data:
			temp = temp1.data
			temp1.data = temp2.data
			temp2.data = temp
		temp2 = temp2.next
		if temp2 == None:
			temp1 = temp1.next
			temp2 = temp1.next
	return h1


def sort(h1):
	nod = h1
	while nod.next:
		index = nod.next
		while index:
			if nod.data > index.data:
				temp = index.data
				index.data = nod.data
				nod.data = temp
			index = index.next
		nod = nod.next
	return h1


def findMid(head):
	slow = head
	fast = head
	while fast.next:
		slow = slow.next
		fast = fast.next
		if fast.next:
			fast = fast.next
	return slow

def merge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	ans = Node(-1)
	temp = ans
	while head and head2:
		if head1.data < head2.data:
			temp.next = head1
			temp = head1
			head1 = head1.next
		else:
			temp.next = head2
			temp = head2
			head2 = head2.next
	while head1:
		temp.next = head1
		temp = head1
		head1 = head1.next
	while head2:
		temp.next = head2
		temp = head2
		head2 = head2.next
	return ans.next

def sort(h1):
	l = []
	temp1 = h1
	while temp1:
		l.append(temp1.data)
		temp1 = temp1.next
	j = 0
	l.sort()
	temp = h1
	while temp:
		temp.data = l[j]
		j += 1
		temp = temp.next
	return h1


def sort(h1):
	odd = []
	even = []
	temp = h1
	count = 0
	while temp:
		count += 1
		if count % 2 == 1:
			odd.append(temp.data)
		else:
			even.append(temp.data)
		temp = temp.next
	tot = even + odd
	tot.sort()
	headcopy = h1
	for i in tot:
		h1.data = i
		h1 = h1.next
	return headcopy


def sort(head):
	a = head
	b = []
	c = Llist()
	curr = None
	while a:
		b.append(a.data)
		a = a.next
	b.sort()
	for i in range(len(b)):
		curr = c.insert(b[i], curr)
	return c.head


def sort(h1):
	if h1 == None or h1.next is None:
		return h1
	ptr = h1
	li = []
	while ptr:
		li.append(ptr.data)
		ptr = ptr.next
	li.sort()
	i = 0
	curr = h1
	while curr:
		curr.data = li[i]
		curr = curr.next
		i += 1
	return h1


import collections

def sort(node):
	values = []
	head = node
	while node:
		values.append(node.data)
		node = node.next
	values.sort()
	values = collections.deque(values)
	node = head
	while node:
		node.data = values.popleft()
		node = node.next
	return head


def sort(h1):
	l = []
	t = h1
	while t:
		l.append(t.data)
		t = t.next
	l = sorted(l)
	t = h1
	for i in l:
		t.data = i
		t = t.next
	return h1


def sort(h1):
	l = []
	temp1 = h1
	while temp1:
		l.append(temp1.data)
		temp1 = temp1.next
	l.sort()
	dummy = Node(0)
	temp0 = dummy
	for i in l:
		temp0.next = Node(i)
		temp0 = temp0.next
	return dummy.next


def sort(head):
	b = []
	while head:
		b.append(head.data)
		head = head.next
	b.sort()
	b.reverse()
	head = Node(0)
	for i in range(len(b)):
		new = Node(b[i])
		new.next = head.next
		head.next = new
	return head.next


def sort(h1):
	ptr = h1
	arr = []
	while ptr != None:
		arr.append(ptr.data)
		ptr = ptr.next
	arr.sort()
	i = 0
	ptr2 = h1
	while ptr2 != None:
		ptr2.data = arr[i]
		ptr2 = ptr2.next
		i += 1
	return h1


def le(h):
	itr = h
	count = 0
	while itr:
		count += 1
		itr = itr.next
	return count

def reverse(h):
	prev = None
	itr = h
	while itr:
		nxt = itr.next
		itr.next = prev
		prev = itr
		itr = next
	return h

def sort(h):
	a = []
	itr = h
	while itr:
		a.append(itr.data)
		itr = itr.next
	a.sort()
	itr = h
	for i in range(len(a)):
		itr.data = a[i]
		itr = itr.next
	return h


def sort(h1):
	tmp = h1
	b = []
	c = []
	while tmp != None:
		b.append(tmp.data)
		tmp = tmp.next
	b.sort()
	tmp = h1
	for i in b:
		tmp.data = i
		tmp = tmp.next
	return h1


def sort(h1):
	curr = h1
	temp = []
	while curr:
		temp.append(curr.data)
		curr = curr.next
	temp.sort()
	dummy = Node(0)
	curr = dummy
	for v in temp:
		curr.next = Node(v)
		curr = curr.next
	return dummy.next


class Node:

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

def sort(h1):
	asc = h1
	dsc = None
	while asc.next and asc.next.next:
		temp = asc.next
		asc.next = asc.next.next
		temp.next = dsc
		asc = asc.next
		dsc = temp
	if asc.next:
		temp = asc.next
		temp.next = dsc
		dsc = temp
		asc.next = None
	res = Node(0)
	cur = res
	while h1 and dsc:
		if h1.data <= dsc.data:
			cur.next = Node(h1.data)
			h1 = h1.next
		else:
			cur.next = Node(dsc.data)
			dsc = dsc.next
		cur = cur.next
	while h1:
		cur.next = Node(h1.data)
		cur = cur.next
		h1 = h1.next
	while dsc:
		cur.next = Node(dsc.data)
		dsc = dsc.next
		cur = cur.next
	return res.next


def sort(h1):
	temp = h1
	arr = []
	while temp:
		arr.append(temp.data)
		temp = temp.next
	arr.sort()
	new = Node(arr[0])
	head = new
	for i in range(1, len(arr)):
		new.next = Node(arr[i])
		new = new.next
	if new.next == None:
		return head


def sort(h1):
	l = []
	while h1:
		l.append(h1.data)
		h1 = h1.next
	l.sort()
	h2 = Node(l[0])
	a = h2
	for i in l[1:]:
		new = Node(i)
		a.next = new
		a = new
	return h2


def sort(h1):
	x = []
	temp = h1
	while temp:
		x.append(temp.data)
		temp = temp.next
	x.sort()
	index = 0
	cur = h1
	while cur:
		cur.data = x[index]
		index += 1
		cur = cur.next
	return h1


def sort(h1):
	temp = temp1 = h1
	K = []
	while h1:
		K.append(h1.data)
		h1 = h1.next
	K.sort()
	L1 = Llist()
	for i in K:
		temp.data = i
		temp = temp.next
	return temp1


def merge(left, right):
	if not left:
		return right
	elif not right:
		return left
	cur = temp = Node(-1)
	while left != None and right != None:
		if left.data < right.data:
			cur.next = left
			left = left.next
		else:
			cur.next = right
			right = right.next
		cur = cur.next
	if left != None:
		cur.next = left
	elif right != None:
		cur.next = right
	return temp.next

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


def sort(h1):
	current = h1
	index = 0
	while current != None:
		index = current.next
		while index != None:
			if current.data > index.data:
				temp = current.data
				current.data = index.data
				index.data = temp
			index = index.next
		current = current.next
	return h1


def sort(head):
	(ps, pe, qs, qe) = (None, None, None, None)
	(i, t) = (1, head)
	while t:
		if i % 2 != 0:
			if ps == None:
				(ps, pe) = (t, t)
			else:
				pe.next = t
				pe = t
		elif qs == None:
			(qs, qe) = (t, t)
		else:
			qe.next = t
			qe = t
		t = t.next
		i += 1
	if pe == None or qe == None:
		return head
	(pe.next, qe.next) = (None, None)
	(prev, cur, nextt) = (None, qs, qs.next)
	while cur != qe and nextt:
		cur.next = prev
		(prev, cur, nextt) = (cur, nextt, nextt.next)
	cur.next = prev
	head2 = cur
	head1 = ps
	(p, q) = (ps, head2)
	dummy = Node(0)
	tail = dummy
	while p and q:
		if p.data <= q.data:
			tail.next = p
			p = p.next
		else:
			tail.next = q
			q = q.next
		tail = tail.next
	if p:
		tail.next = p
	if q:
		tail.next = q
	return dummy.next


def sort(head):
	if head == None or head.next == None:
		return head
	fmain = frun = head
	smain = srun = head.next
	while frun.next != None and srun.next != None:
		frun.next = frun.next.next
		frun = frun.next
		if srun.next.next != None:
			srun.next = srun.next.next
			srun = srun.next
	srun.next = frun.next = None
	smain = reverse(smain)
	head = sortedMerge(fmain, smain)
	return head

def sortedMerge(head1, head2):
	if head1 == None or head2 == None:
		primehead = head2 if head1 == None else head1
		return primehead
	primehead = runhead = Node(None)
	while head1 != None and head2 != None:
		if head1.data < head2.data:
			runhead.next = head1
			head1 = head1.next
		else:
			runhead.next = head2
			head2 = head2.next
		runhead = runhead.next
	linknode = head2 if head1 == None else head1
	runhead.next = linknode
	return primehead.next

def reverse(node):
	primenode = None
	while node != None:
		holdnode = node.next
		node.next = primenode
		primenode = node
		node = holdnode
	return primenode


class Node:

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

def sort(h1):
	a = []
	cu = h1
	while cu != None:
		a.append(cu.data)
		cu = cu.next
	a.sort()
	temp = h1
	for i in a:
		temp.data = i
		temp = temp.next
	return h1


def sort(h1):
	if h1.next == None:
		return h1

	def getReverse(head):
		reverse = None
		while head != None:
			nex = head.next
			head.next = reverse
			reverse = head
			head = nex
		return reverse
	temp = h1
	pre = temp
	result = Node(0)
	temp2 = result
	count = 0
	while temp != None:
		if count != 0 and count % 2 == 0:
			pre.next = temp
			pre = temp
		elif count % 2 != 0:
			node = Node(temp.data)
			temp2.next = node
			temp2 = temp2.next
		count += 1
		temp = temp.next
	pre.next = None
	reverse = getReverse(result.next)
	result = Node(0)
	temp = result
	while h1 != None and reverse != None:
		if h1.data < reverse.data:
			node = Node(h1.data)
			h1 = h1.next
		else:
			node = Node(reverse.data)
			reverse = reverse.next
		temp.next = node
		temp = temp.next
	if h1 != None:
		temp.next = h1
	if reverse != None:
		temp.next = reverse
	return result.next


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

def merge(left, right):
	if left is None:
		return right
	if right is None:
		return left
	ans = Node(None)
	temp = ans
	while left != None and right != None:
		if left.data < right.data:
			temp.next = left
			temp = left
			left = left.next
		else:
			temp.next = right
			temp = right
			right = right.next
	while left != None:
		temp.next = left
		temp = left
		left = left.next
	while right != None:
		temp.next = right
		temp = right
		right = right.next
	ans = ans.next
	return ans

def sort(head):
	if head is None or head.next is None:
		return head
	mid = findmid(head)
	left = head
	right = mid.next
	mid.next = None
	left = sort(left)
	right = sort(right)
	result = merge(left, right)
	return result


def sort(h1):
	a = []
	p = h1
	q = h1
	while p:
		a.append(p.data)
		p = p.next
	a1 = sorted(a)
	for i in range(0, len(a)):
		q.data = a1[i]
		q = q.next
	return h1


def sort(h1):
	if h1:
		current = None
		new_head = None
		move_node = None
		prev = None
		while h1 != None:
			prev = None
			current = h1
			move_node = h1
			while current != None:
				if current.next != None and current.next.data > move_node.data:
					move_node = current.next
					prev = current
				current = current.next
			if move_node == h1:
				h1 = h1.next
			if prev != None:
				prev.next = move_node.next
			move_node.next = new_head
			new_head = move_node
		h1 = new_head
		return h1