Sort the given Linked List using quicksort. which takes O(n^2) time in worst case and O(nLogn) in average and best cases, otherwise you may get TLE.
Input:
In this problem, method takes 1 argument: address of the head of the linked list. The function should not read any input from stdin/console.
The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list.
There are multiple test cases. For each test case, this method will be called individually.
Output:
Set *headRef to head of resultant linked list.
User Task:
The task is to complete the function quickSort() which should set the *headRef to head of the resultant linked list.
Constraints:
1<=T<=100
1<=N<=200
Note: If you use "Test" or "Expected Output Button" use below example format
Example:
Input:
2
3
1 6 2
4
1 9 3 8
Output:
1 2 6
1 3 8 9
Explanation:
Testcase 1: After sorting the nodes, we have 1, 2 and 6.
Testcase 2: After sorting the nodes, we have 1, 3, 8 and 9.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:
#User function Template for python3

def quickSort(head):
    #return head after sorting

Solutions:
class Node:

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

def quickSort(head):
	if head is None or head.next is None:
		return head
	pivot = head
	current = head.next
	less_than_pivot = None
	greater_than_pivot = None
	while current is not None:
		next_node = current.next
		if current.data < pivot.data:
			current.next = less_than_pivot
			less_than_pivot = current
		else:
			current.next = greater_than_pivot
			greater_than_pivot = current
		current = next_node
	less_than_pivot = quickSort(less_than_pivot)
	greater_than_pivot = quickSort(greater_than_pivot)
	pivot.next = greater_than_pivot
	if less_than_pivot is None:
		return pivot
	sorted_head = less_than_pivot
	while less_than_pivot.next is not None:
		less_than_pivot = less_than_pivot.next
	less_than_pivot.next = pivot
	return sorted_head


def quickSort(head):
	if head is None:
		return
	elif head.next is None:
		return head
	data = partition(head)
	left = quickSort(data[0])
	right = quickSort(data[2])
	tmp = left
	while left is not None and left.next is not None:
		left = left.next
	if left is not None:
		left.next = data[1]
	else:
		tmp = data[1]
	data[1].next = right
	while right is not None and right.next is not None:
		right = right.next
	if right is not None:
		right.next = None
	return tmp

def partition(head):
	pivot = head
	left = Node(None)
	right = Node(None)
	tempLeft = left
	tempRight = right
	head = head.next
	while head is not None:
		if head.data <= pivot.data:
			left.next = head
			left = left.next
		else:
			right.next = head
			right = right.next
		head = head.next
	left.next = None
	right.next = None
	return [tempLeft.next, pivot, tempRight.next]


def quickSort(head):

	def quick(head):
		if head == None:
			return None
		tail = head
		last = None
		while tail.next:
			last = tail
			tail = tail.next
		if tail == head:
			return head
		last.next = None
		n2 = None
		n1 = None
		while head:
			node = head
			head = head.next
			node.next = None
			if node.data > tail.data:
				node.next = n2
				n2 = node
			else:
				node.next = n1
				n1 = node
		n1 = quick(n1)
		n2 = quick(n2)
		if n1:
			node = n1
			while node.next:
				node = node.next
			node.next = tail
			tail.next = n2
		else:
			tail.next = n2
			n1 = tail
		return n1
	return quick(head)


def quickSort(head):
	(head, tail) = qs(head)
	return head

def qs(head):
	if not head.next:
		return (head, head)
	(head_lower, tail_lower, pivot, head_higher) = partition(head)
	if head_lower:
		(head_lower, tail_lower) = qs(head_lower)
	tail_higher = None
	if head_higher:
		(head_higher, tail_higher) = qs(head_higher)
	if tail_lower:
		tail_lower.next = pivot
	else:
		head_lower = pivot
	if not head_higher:
		tail_higher = pivot
	pivot.next = head_higher
	return (head_lower, tail_higher)

def printll(head):
	if not head:
		return
	while head:
		print(head.data, end=' ')
		head = head.next
	print()

def partition(head):
	pivot = head
	head_lower = None
	tail_lower = None
	head_higher = None
	tail_higher = None
	curr = pivot.next
	pivot.next = None
	while curr:
		next = curr.next
		if curr.data <= pivot.data:
			if tail_lower:
				tail_lower.next = curr
				tail_lower = curr
			else:
				head_lower = curr
				tail_lower = curr
			curr.next = None
		else:
			if tail_higher:
				tail_higher.next = curr
				tail_higher = curr
			else:
				head_higher = curr
				tail_higher = curr
			curr.next = None
		curr = next
	return (head_lower, tail_lower, pivot, head_higher)


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


def quickSort(head):
	P = []
	a = head
	while a:
		P.append([a, a.data])
		a = a.next
	P.sort(key=lambda x: x[1])
	for i in range(len(P) - 1):
		P[i][0].next = P[i + 1][0]
	P[len(P) - 1][0].next = None
	return P[0][0]


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

def quickSort(head):
	return mergesort(head)


def quickSort(head):
	if not head or not head.next:
		return head
	pivot = head
	smallhead = small = Node(-1)
	largehead = large = Node(-1)
	curr = head.next
	while curr:
		if curr == pivot:
			curr = curr.next
		elif curr.data < pivot.data:
			small.next = curr
			curr = curr.next
			small = small.next
		else:
			large.next = curr
			curr = curr.next
			large = large.next
	small.next = None
	large.next = None
	small = quickSort(smallhead.next)
	pivot.next = None
	large = quickSort(largehead.next)
	temp = small
	while temp and temp.next:
		temp = temp.next
	if temp:
		temp.next = pivot
	else:
		small = pivot
	pivot.next = large
	return small


def quickSort(head):
	if head == None or head.next == None:
		return head
	p = []
	(a, temp) = (head, head)
	while a:
		p.append([a, a.data])
		a = a.next
	p.sort(key=lambda x: x[1])
	for j in range(len(p) - 1):
		p[j][0].next = p[j + 1][0]
	p[j + 1][0].next = None
	return p[0][0]


def quickSort(head):
	if not head or not head.next:
		return head
	p = head
	shead = small = Node(-1)
	lhead = large = Node(-1)
	curr = head.next
	while curr:
		if curr == p:
			curr = curr.next
		elif curr.data < p.data:
			small.next = curr
			curr = curr.next
			small = small.next
		else:
			large.next = curr
			curr = curr.next
			large = large.next
	small.next = None
	large.next = None
	small = quickSort(shead.next)
	p.next = None
	large = quickSort(lhead.next)
	temp = small
	while temp and temp.next:
		temp = temp.next
	if temp:
		temp.next = p
	else:
		small = p
	p.next = large
	return small


def partition(head, tail):
	pivot = head.data
	prev = head
	curr = head.next
	while curr != tail.next:
		if curr.data < pivot:
			(prev.next.data, curr.data) = (curr.data, prev.next.data)
			prev = prev.next
		curr = curr.next
	(prev.data, head.data) = (head.data, prev.data)
	return prev

def solveSort(head, tail):
	if head == None or tail == None or head == tail:
		return
	pivot = partition(head, tail)
	solveSort(head, pivot)
	solveSort(pivot.next, tail)

def quickSort(head):
	if head == None or head.next == None:
		return head
	tail = head
	while tail and tail.next:
		tail = tail.next
	solveSort(head, tail)


def quickSort(head):
	curr = head
	tmp = []
	if curr == None:
		return
	while curr != None:
		tmp.append(curr.data)
		curr = curr.next
	d = sorted(tmp)
	for i in d:
		print(i, end=' ')


def quickSort(head):
	start = Node(0)
	start.next = head
	while head.next:
		head = head.next
	(first, last) = helper(start.next, head)
	return first

def helper(start, end):
	if start == end:
		return (start, end)
	pivot = start
	left = Node(0)
	left_start = left
	right = Node(0)
	right_start = right
	while start != end:
		if start.next.data < pivot.data:
			left.next = start.next
			left = left.next
		else:
			right.next = start.next
			right = right.next
		start = start.next
	if left_start.next:
		(left_start, left_end) = helper(left_start.next, left)
		left_end.next = pivot
	else:
		left_start = pivot
	if right_start.next:
		(right_start, right_end) = helper(right_start.next, right)
		pivot.next = right_start
	else:
		right_end = pivot
	right_end.next = None
	return (left_start, right_end)


def quickSort(head):
	if head == None or head.next == None:
		return head
	mid = findmid(head)
	leftpart = head
	rightpart = mid.next
	mid.next = None
	left = quickSort(leftpart)
	right = quickSort(rightpart)
	ans = merge(left, right)
	return ans

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

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.next = left
			temp = left
			left = left.next
		else:
			temp.next = right
			temp = right
			right = right.next
	if left != None:
		temp.next = left
		temp = left
		left = left.next
	if right != None:
		temp.next = right
		temp = right
		right = right.next
	return ans.next


def partition(head, pivt):
	val_head = head
	prev = head
	while head != pivt:
		if head.data < pivt.data:
			(head.data, val_head.data) = (val_head.data, head.data)
			prev = val_head
			val_head = val_head.next
		head = head.next
	(pivt.data, val_head.data) = (val_head.data, pivt.data)
	return prev

def quick(head, pivot):
	if head != pivot:
		pr = partition(head, pivot)
		quick(head, pr)
		quick(pr.next, pivot)

def quickSort(head):
	curr = head
	while curr.next:
		curr = curr.next
	quick(head, curr)
	while head:
		print(head.data, end=' ')
		head = head.next


def quickSort(head):
	ans = head
	arr = []
	while head != None:
		arr.append(head.data)
		head = head.next
	arr.sort()
	print(*arr, end='')


def quickSort(head):
	if not head or not head.next:
		return head
	pivot = head
	lefts = left = Node(-1)
	rights = right = Node(-1)
	curr = head.next
	while curr:
		if curr == pivot:
			curr = curr.next
		elif curr.data < pivot.data:
			left.next = curr
			curr = curr.next
			left = left.next
		else:
			right.next = curr
			curr = curr.next
			right = right.next
	left.next = None
	right.next = None
	left = quickSort(lefts.next)
	pivot.next = None
	right = quickSort(rights.next)
	temp = left
	while temp and temp.next:
		temp = temp.next
	if temp:
		temp.next = pivot
	else:
		left = pivot
	pivot.next = right
	return left


def quickSort(head):
	p = head
	while p != None:
		q = head
		while q != None and q.next != None:
			if q.data > q.next.data:
				t = q.data
				q.data = q.next.data
				q.next.data = t
			q = q.next
		p = p.next
	t = head
	while t != None:
		print(t.data, end=' ')
		t = t.next


def quickSort(head):

	def partition(head, tail, prev):
		if not head:
			return tail
		if not tail:
			return head
		if head == tail or head == tail.next:
			return head
		curr = head
		dummy = Node(data=None) if not prev else prev
		dummy.next = head
		prev = dummy
		end = tail
		while curr != tail:
			if curr.data > tail.data:
				prev.next = curr.next
				curr.next = end.next
				end.next = curr
				end = curr
				curr = prev.next
			else:
				prev = curr
				curr = curr.next
		(lstart, lend) = (dummy.next, prev)
		(rstart, rend) = (tail.next, end)
		left = partition(lstart, lend, dummy)
		partition(rstart, rend, tail)
		return left
	tail = head
	while tail.next:
		tail = tail.next
	return partition(head, tail, None)


def partition(head, tail, prev):
	if not head:
		return tail
	if not tail:
		return head
	if head == tail or head == tail.next:
		return head
	cur = head
	temp = Node(data=None) if not prev else prev
	temp.next = head
	prev = temp
	end = tail
	while cur != tail:
		if cur.data > tail.data:
			prev.next = cur.next
			cur.next = end.next
			end.next = cur
			end = cur
			cur = prev.next
		else:
			prev = cur
			cur = cur.next
		(lst, lend) = (temp.next, prev)
		(rst, rend) = (tail.next, end)
		left = partition(lst, lend, temp)
		partition(rst, rend, tail)
		return left

def quickSort(head):
	if not head or not head.next:
		return head
	pivot = head
	smallhead = small = Node(-1)
	largehead = large = Node(-1)
	curr = head.next
	while curr:
		if curr == pivot:
			curr = curr.next
		elif curr.data < pivot.data:
			small.next = curr
			curr = curr.next
			small = small.next
		else:
			large.next = curr
			curr = curr.next
			large = large.next
	small.next = None
	large.next = None
	small = quickSort(smallhead.next)
	pivot.next = None
	large = quickSort(largehead.next)
	temp = small
	while temp and temp.next:
		temp = temp.next
	if temp:
		temp.next = pivot
	else:
		small = pivot
	pivot.next = large
	return small


def quickSort(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 = quickSort(head)
	head2 = quickSort(mid)
	merged_list = merge(head1, head2)
	return merged_list

def merge(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


def quickSort(head):
	if head is None:
		return None
	(h, t) = mysort(head)
	t.next = None
	return h

def mysort(head):
	if head is None:
		return (None, None)
	if head and head.next is None:
		return (head, head)
	left = None
	pleft = None
	right = None
	pright = None
	phead = head
	p = head.next
	while p:
		if p.data < head.data:
			if left is None:
				left = p
				pleft = p
				p = p.next
				pleft.next = None
			else:
				pleft.next = p
				pleft = p
				p = p.next
				pleft.next = None
		elif p.data > head.data:
			if right is None:
				right = p
				pright = p
				p = p.next
				pright.next = None
			else:
				pright.next = p
				pright = p
				p = p.next
				pright.next = None
		elif p.data == head.data:
			phead.next = p
			phead = p
			p = p.next
			phead.next = None
	(lhead, ltail) = mysort(left)
	(rhead, rtail) = mysort(right)
	if lhead is None and rhead is None:
		return (head, phead)
	if lhead is None and rhead is not None:
		phead.next = rhead
		return (head, rtail)
	elif lhead and rhead is None:
		ltail.next = head
		return (lhead, phead)
	elif lhead and rhead:
		ltail.next = head
		phead.next = rhead
		return (lhead, rtail)


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

def merge(h1, h2):
	if h1 == None:
		return h2
	if h2 == None:
		return h1
	h = t = None
	if h1.data <= h2.data:
		h = t = h1
		h1 = h1.next
	else:
		h = t = h2
		h2 = h2.next
	while h1 and h2:
		if h1.data <= h2.data:
			t.next = h1
			t = t.next
			h1 = h1.next
		else:
			t.next = h2
			t = t.next
			h2 = h2.next
	while h1:
		t.next = h1
		t = t.next
		h1 = h1.next
	while h2:
		t.next = h2
		t = t.next
		h2 = h2.next
	t.next = None
	return h

def mergeSort(head):
	if head == None or head.next == None:
		return head
	h1 = head
	mid = getMid(head)
	h2 = mid.next
	mid.next = None
	head1 = mergeSort(h1)
	head2 = mergeSort(h2)
	return merge(head1, head2)

def quickSort(head):
	return mergeSort(head)


def quickSort(head):
	if head is None or head.next is None:
		return head
	piv = head
	left = []
	right = []
	n = head.next
	while n:
		if n.data < piv.data:
			left.append(n)
		else:
			right.append(n)
		n = n.next
	L = None
	curr = None
	for e in left:
		if curr is None:
			L = e
			curr = L
		else:
			curr.next = e
			curr = curr.next
	if curr:
		curr.next = None
	R = None
	curr = None
	for p in right:
		if curr is None:
			R = p
			curr = R
		else:
			curr.next = p
			curr = curr.next
	if curr:
		curr.next = None
	if len(left) > 0:
		leftLL = quickSort(L)
	else:
		leftLL = quickSort(None)
	if len(right) > 0:
		rightLL = quickSort(R)
	else:
		rightLL = quickSort(None)
	final = None
	if leftLL:
		final = leftLL
		n = leftLL
		while n.next:
			n = n.next
		piv.next = rightLL
		n.next = piv
	else:
		final = piv
		piv.next = rightLL
	return final


def quickSort(head):
	if head is None or head.next is None:
		return head
	piv = head
	left = []
	right = []
	n = head.next
	while n:
		if n.data < piv.data:
			left.append(n)
		else:
			right.append(n)
		n = n.next
	L = None
	curr = None
	for i in range(len(left)):
		if i == len(left) - 1:
			left[i].next = None
		else:
			left[i].next = left[i + 1]
	for i in range(len(right)):
		if i == len(right) - 1:
			right[i].next = None
		else:
			right[i].next = right[i + 1]
	if len(left) > 0:
		leftLL = quickSort(left[0])
	else:
		leftLL = quickSort(None)
	if len(right) > 0:
		rightLL = quickSort(right[0])
	else:
		rightLL = quickSort(None)
	final = None
	if leftLL:
		final = leftLL
		n = leftLL
		while n.next:
			n = n.next
		piv.next = rightLL
		n.next = piv
	else:
		final = piv
		piv.next = rightLL
	return final


def quickSort(head):
	if head == None or head.next == None:
		return head
	pivot = head
	left = leftHead = Node(-1)
	right = rightHead = Node(-1)
	curr = head.next
	while curr:
		if curr == pivot:
			curr = curr.next
		elif curr.data < pivot.data:
			left.next = curr
			curr = curr.next
			left = left.next
		else:
			right.next = curr
			curr = curr.next
			right = right.next
	left.next = None
	right.next = None
	left = quickSort(leftHead.next)
	pivot.next = None
	right = quickSort(rightHead.next)
	temp = left
	while temp and temp.next:
		temp = temp.next
	if temp:
		temp.next = pivot
	else:
		left = pivot
	pivot.next = right
	return left


def quickSort(head):
	if head == None or head.next == None:
		return head
	piv = head
	left = []
	right = []
	n = head.next
	while n:
		if n.data < piv.data:
			left.append(n)
		else:
			right.append(n)
		n = n.next
	for i in range(len(left)):
		if i == len(left) - 1:
			left[i].next = None
		else:
			left[i].next = left[i + 1]
	for i in range(len(right)):
		if i == len(right) - 1:
			right[i].next = None
		else:
			right[i].next = right[i + 1]
	if len(left) > 0:
		leftLL = quickSort(left[0])
	else:
		leftLL = quickSort(None)
	if len(right) > 0:
		rightLL = quickSort(right[0])
	else:
		rightLL = quickSort(None)
	if leftLL == None:
		newhead = piv
		piv.next = rightLL
	else:
		newhead = leftLL
		n = leftLL
		while n.next:
			n = n.next
		piv.next = rightLL
		n.next = piv
	return newhead


def quickSort(head):
	curr = head
	if curr == None and curr.next == None:
		return head
	while curr:
		temp = curr.next
		while temp:
			if temp.data < curr.data:
				(curr.data, temp.data) = (temp.data, curr.data)
			temp = temp.next
		curr = curr.next
	while head:
		print(head.data, end=' ')
		head = head.next


def quickSortDC(head):
	if not head.next:
		return [head, head]
	foo1 = head
	foo2 = head
	tmp1 = foo1.next
	head1 = None
	tail1 = None
	head2 = None
	tail2 = None
	while tmp1:
		if tmp1.data <= foo1.data:
			if head1 is None:
				head1 = tmp1
				tail1 = tmp1
			else:
				tail1.next = tmp1
				tail1 = tail1.next
		elif head2 is None:
			head2 = tmp1
			tail2 = tmp1
		else:
			tail2.next = tmp1
			tail2 = tail2.next
		tmp1 = tmp1.next
	if head1 is not None:
		tail1.next = None
		(head1, tail1) = quickSortDC(head1)
		tail1.next = None
	if head2 is not None:
		tail2.next = None
		(head2, tail2) = quickSortDC(head2)
		tail2.next = None
	head.next = None
	if head1 is None:
		head.next = head2
		return [head, tail2]
	elif head2 is None:
		tail1.next = head
		return [head1, head]
	else:
		tail1.next = head
		head.next = head2
		return [head1, tail2]

def quickSort(head):
	(head, tail) = quickSortDC(head)
	return head


def merge(head1, head2):
	l1 = head1
	l2 = head2
	head = None
	end = None
	union = []
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	while l1 is not None and l2 is not None:
		if l1.data < l2.data:
			if head is None:
				head = l1
				end = l1
			else:
				end.next = l1
				end = end.next
			l1 = l1.next
			end.next = None
		else:
			if head is None:
				head = l2
				end = l2
			else:
				end.next = l2
				end = end.next
			l2 = l2.next
			end.next = None
	if l1 is None and l2 is None:
		return head
	elif l1 is None:
		end.next = l2
	else:
		end.next = l1
	return head

def sort_list(head):
	if head is None:
		return head
	if head.next is None:
		return head
	if head.next.next is None:
		if head.data > head.next.data:
			head.next.next = head
			head = head.next
			head.next.next = None
		return head
	fast = head
	slow = head
	while fast != None and fast.next != None:
		fast = fast.next
		slow = slow.next
		fast = fast.next
	head2 = slow.next
	slow.next = None
	head1 = sort_list(head)
	head2 = sort_list(head2)
	head_f = merge(head1, head2)
	return head_f

def quickSort(head):
	return sort_list(head)


def quickSort(head):
	curr = head
	while curr:
		temp = curr.next
		while temp:
			if curr.data > temp.data:
				(curr.data, temp.data) = (temp.data, curr.data)
			temp = temp.next
		curr = curr.next
	while head:
		print(head.data, end=' ')
		head = head.next


def quickSort(head):
	if head is None or head.next is None:
		return head
	pivot = head
	lefthead = left = Node(-1)
	righthead = right = Node(-1)
	curr = head.next
	while curr:
		if curr.data < pivot.data:
			left.next = curr
			left = left.next
		else:
			right.next = curr
			right = right.next
		curr = curr.next
	left.next = None
	right.next = None
	left = quickSort(lefthead.next)
	right = quickSort(righthead.next)
	pivot.next = None
	itr = left
	while itr and itr.next:
		itr = itr.next
	if itr:
		itr.next = pivot
	else:
		left = pivot
	pivot.next = right
	return left


def partition(arr, brr, low, high):
	count = 0
	for i in range(low, high + 1):
		if arr[i] < arr[low]:
			count += 1
	p = low + count
	temp1 = arr[low]
	arr[low] = arr[p]
	arr[p] = temp1
	temp2 = brr[low]
	brr[low] = brr[p]
	brr[p] = temp2
	i = low
	j = high
	while i < j:
		if arr[i] >= arr[p] and arr[j] < arr[p]:
			temp3 = arr[i]
			arr[i] = arr[j]
			arr[j] = temp3
			temp4 = brr[i]
			brr[i] = brr[j]
			brr[j] = temp4
		elif arr[i] >= arr[p]:
			j -= 1
		elif arr[j] < arr[p]:
			i += 1
		else:
			i += 1
			j -= 1
	return p

def solve(arr, brr, low, high):
	if low >= high:
		return
	p = partition(arr, brr, low, high)
	a = solve(arr, brr, low, p - 1)
	b = solve(arr, brr, p + 1, high)
	return brr

def quickSort(head):
	if head.next == None:
		return head
	arr = []
	brr = []
	curr = head
	while curr:
		arr.append(curr.data)
		brr.append(curr)
		curr = curr.next
	low = 0
	high = len(arr) - 1
	brr = solve(arr, brr, low, high)
	for i in range(len(brr)):
		if i == len(brr) - 1:
			brr[i].next = None
			break
		brr[i].next = brr[i + 1]
	return brr[0]


def quickSort(head):
	if not head or not head.next:
		return head
	pivot = head
	lh = l = Node(0)
	rh = r = Node(0)
	cur = head.next
	while cur:
		if cur == pivot:
			cur = cur.next
		elif cur.data < pivot.data:
			l.next = cur
			cur = cur.next
			l = l.next
		else:
			r.next = cur
			cur = cur.next
			r = r.next
	l.next = None
	r.next = None
	l = quickSort(lh.next)
	pivot.next = None
	r = quickSort(rh.next)
	cur = l
	while cur and cur.next:
		cur = cur.next
	if cur:
		cur.next = pivot
	else:
		l = pivot
	pivot.next = r
	return l


def quickSort(head):
	curr = head
	if curr is None:
		return head
	while curr:
		nxt = curr.next
		while nxt:
			if curr.data > nxt.data:
				(curr.data, nxt.data) = (nxt.data, curr.data)
			nxt = nxt.next
		curr = curr.next
	curr = head
	while curr:
		print(curr.data, end=' ')
		curr = curr.next


def quickSort(head):
	cur = head
	a = []
	while cur:
		a.append(cur.data)
		cur = cur.next

	def part(a, l, r):
		pivot = a[r]
		i = l - 1
		for j in range(l, r):
			if a[j] <= pivot:
				i += 1
				(a[i], a[j]) = (a[j], a[i])
		(a[i + 1], a[r]) = (a[r], a[i + 1])
		return i + 1

	def quick(a, l, r):
		if l < r:
			p = part(a, l, r)
			quick(a, l, p - 1)
			quick(a, p + 1, r)
	quick(a, 0, len(a) - 1)
	for i in a:
		print(i, end=' ')


def quickSort(head):
	temp = head
	a = []
	if temp is None:
		return head
	while temp:
		p = temp.next
		while p:
			if temp.data > p.data:
				(temp.data, p.data) = (p.data, temp.data)
			p = p.next
		temp = temp.next
	temp = head
	while temp:
		print(temp.data, end=' ')
		temp = temp.next


def seg(head, pivotidx):
	small = Node(-1)
	large = Node(-1)
	(curr, sp, lp, pivotnode) = (head, small, large, head)
	while pivotidx > 0:
		pivotnode = pivotnode.next
		pivotidx -= 1
	while curr != None:
		if curr != pivotnode:
			if curr.data <= pivotnode.data:
				sp.next = curr
				sp = sp.next
			else:
				lp.next = curr
				lp = lp.next
		curr = curr.next
	sp.next = None
	lp.next = None
	pivotnode.next = None
	return (small.next, pivotnode, large.next)

def length(head):
	if head is None:
		return 0
	curr = head
	count = 0
	while curr != None:
		curr = curr.next
		count += 1
	return count

def merge(leftsortedlisthead, leftsortedlisttail, pivotnode, rightsortedlisthead, rightsortedlisttail):
	head = None
	tail = None
	if leftsortedlisthead != None and rightsortedlisthead != None:
		leftsortedlisttail.next = pivotnode
		pivotnode.next = rightsortedlisthead
		head = leftsortedlisthead
		tail = rightsortedlisttail
	elif leftsortedlisthead != None:
		head = leftsortedlisthead
		leftsortedlisttail.next = pivotnode
		tail = pivotnode
	elif rightsortedlisthead != None:
		head = pivotnode
		pivotnode.next = rightsortedlisthead
		tail = rightsortedlisttail
	else:
		head = pivotnode
		tail = pivotnode
	return (head, tail)

def result(head):
	if head is None or head.next is None:
		return (head, head)
	lent = length(head)
	pivotidx = lent // 2
	(leftsort, pivotnode, rightsort) = seg(head, pivotidx)
	(leftsortedlisthead, leftsortedlisttail) = result(leftsort)
	(rightsortedlisthead, rightsortedlisttail) = result(rightsort)
	(head, tail) = merge(leftsortedlisthead, leftsortedlisttail, pivotnode, rightsortedlisthead, rightsortedlisttail)
	return (head, tail)

def quickSort(head):
	(head, tail) = result(head)
	return head


def sortedmerge(a, b):
	res = None
	if a == None:
		return b
	elif b == None:
		return a
	if a.data < b.data:
		res = a
		res.next = sortedmerge(a.next, b)
	else:
		res = b
		res.next = sortedmerge(a, b.next)
	return res

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

def mergeSort(head):
	if head == None or head.next == None:
		return head
	mid = middle(head)
	new_head = mid.next
	mid.next = None
	left = mergeSort(head)
	right = mergeSort(new_head)
	x = sortedmerge(left, right)
	return x

def quickSort(head):
	return mergeSort(head)


def _swap(i, j, pi, pj):
	if i == j:
		return
	elif i.next == j:
		aj = j.next
		pi.next = j
		j.next = i
		i.next = aj
	else:
		aj = j.next
		ai = i.next
		pi.next = j
		j.next = ai
		pj.next = i
		i.next = aj

def _qsort(guard, L, R):
	if R == guard or not R or L == R:
		return
	pv = R.data
	i = j = L
	pi = pj = guard
	while j != R:
		if j.data <= pv:
			_swap(i, j, pi, pj)
			(i, j) = (j, i)
			pi = i
			i = i.next
		pj = j
		j = j.next
	Rprev = guard.next
	while Rprev.next != R:
		Rprev = Rprev.next
	_swap(i, R, pi, Rprev)
	(i, R) = (R, i)
	_qsort(guard, guard.next, pi)
	_qsort(i, i.next, R)

def quickSort(head):
	tail = head
	while tail.next:
		tail = tail.next
	guard = Node(-1)
	guard.next = head
	_qsort(guard, head, tail)
	return guard.next


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


def quickSort(head):

	def partition(di, low, high):
		pi = di[high]
		i = low - 1
		j = low
		while j < high:
			if di[j].data < pi.data:
				i += 1
				(di[i], di[j]) = (di[j], di[i])
			j += 1
		(di[i + 1], di[high]) = (di[high], di[i + 1])
		return i + 1

	def qs(di, low, high):
		if low < high:
			pi = partition(di, low, high)
			qs(di, low, pi - 1)
			qs(di, pi + 1, high)
	di = {}
	curr = head
	i = 0
	while curr:
		di[i] = curr
		curr = curr.next
		i += 1
	l = i
	qs(di, 0, l - 1)
	for i in range(1, l):
		di[i - 1].next = di[i]
	di[l - 1].next = None
	return di[0]


def quickSort(head):
	temp = head
	l = []
	while temp is not None:
		l.append([temp.data, temp])
		temp = temp.next
	l.sort(key=lambda x: x[0])
	n = len(l)
	for i in range(n - 1):
		l[i][1].next = l[i + 1][1]
	l[n - 1][1].next = None
	return l[0][1]
from collections import defaultdict

class Node:

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

class Llist:

	def __init__(self):
		self.head = None

	def insert(self, data, tail):
		node = Node(data)
		if not self.head:
			self.head = node
			return node
		tail.next = node
		return node

def nodeID(head, dic):
	while head:
		dic[head.data].append(id(head))
		head = head.next

def printList(head, dic):
	while head:
		if id(head) not in dic[head.data]:
			print("Do'nt swap data, swap pointer/node")
			return
		print(head.data, end=' ')
		head = head.next
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ll = Llist()
		tail = None
		for nodeData in arr:
			tail = ll.insert(nodeData, tail)
		dic = defaultdict(list)
		nodeID(ll.head, dic)
		resHead = quickSort(ll.head)
		printList(resHead, dic)
		print()


def quickSort(head):
	if not head or not head.next:
		return head
	pivot = head
	smallhead = small = Node(-1)
	largehead = large = Node(-1)
	curr = head.next
	while curr:
		if curr == pivot:
			curr = curr.next
		elif curr.data < pivot.data:
			small.next = curr
			curr = curr.next
			small = small.next
		else:
			large.next = curr
			large = large.next
			curr = curr.next
	small.next = None
	large.next = None
	small = quickSort(smallhead.next)
	pivot.next = None
	large = quickSort(largehead.next)
	temp = small
	while temp and temp.next:
		temp = temp.next
	if temp:
		temp.next = pivot
	else:
		small = pivot
	pivot.next = large
	return small
from collections import defaultdict

class Node:

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

class Llist:

	def __init__(self):
		self.head = None

	def insert(self, data, tail):
		node = Node(data)
		if not self.head:
			self.head = node
			return node
		tail.next = node
		return node

def nodeID(head, dic):
	while head:
		dic[head.data].append(id(head))
		head = head.next

def printList(head, dic):
	while head:
		if id(head) not in dic[head.data]:
			print("Do'nt swap data, swap pointer/node")
			return
		print(head.data, end=' ')
		head = head.next
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ll = Llist()
		tail = None
		for nodeData in arr:
			tail = ll.insert(nodeData, tail)
		dic = defaultdict(list)
		nodeID(ll.head, dic)
		resHead = quickSort(ll.head)
		printList(resHead, dic)
		print()


def quick(l, lb, ub):
	if lb < ub:
		loc = partition(l, lb, ub)
		quick(l, loc + 1, ub)
		quick(l, lb, loc - 1)

def partition(l, lb, ub):
	pivot = l[lb]
	start = lb
	end = ub
	while start < end:
		while l[start] <= pivot and start < end:
			start += 1
		while l[end] > pivot:
			end -= 1
		if start < end:
			(l[start], l[end]) = (l[end], l[start])
	(l[end], l[lb]) = (l[lb], l[end])
	return end

def display(head):
	temp = head
	while temp:
		print(temp.data, end=' ')
		temp = temp.next

def quickSort(head):
	l = []
	temp = head
	while temp:
		l.append(temp.data)
		temp = temp.next
	quick(l, 0, len(l) - 1)
	temp = head
	s = 0
	while temp:
		temp.data = l[s]
		temp = temp.next
		s += 1
	display(head)
from collections import defaultdict

class Node:

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

class Llist:

	def __init__(self):
		self.head = None

	def insert(self, data, tail):
		node = Node(data)
		if not self.head:
			self.head = node
			return node
		tail.next = node
		return node

def nodeID(head, dic):
	while head:
		dic[head.data].append(id(head))
		head = head.next

def printList(head, dic):
	while head:
		if id(head) not in dic[head.data]:
			print("Do'nt swap data, swap pointer/node")
			return
		print(head.data, end=' ')
		head = head.next
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ll = Llist()
		tail = None
		for nodeData in arr:
			tail = ll.insert(nodeData, tail)
		dic = defaultdict(list)
		nodeID(ll.head, dic)
		resHead = quickSort(ll.head)
		printList(resHead, dic)
		print()


def quickSort(head):

	def sort(n):
		if n.next == None:
			return n
		pivot = n
		itr = n.next
		pivot.next = None
		l = None
		r = None
		itrL = l
		itrR = r
		while itr:
			if itr.data < pivot.data:
				x = itr
				itr = itr.next
				x.next = None
				if l == None:
					l = x
					itrL = l
				else:
					itrL.next = x
					itrL = itrL.next
			else:
				x = itr
				itr = itr.next
				x.next = None
				if r == None:
					r = x
					itrR = r
				else:
					itrR.next = x
					itrR = itrR.next
		if l != None and l.next != None:
			l = sort(l)
			while itrL.next != None:
				itrL = itrL.next
		if r != None and r.next != None:
			r = sort(r)
			while itrR.next != None:
				itrR = itrR.next
		if l != None:
			itrL.next = pivot
			pivot.next = r
			return l
		else:
			pivot.next = r
			return pivot
	return sort(head)
from collections import defaultdict

class Node:

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

class Llist:

	def __init__(self):
		self.head = None

	def insert(self, data, tail):
		node = Node(data)
		if not self.head:
			self.head = node
			return node
		tail.next = node
		return node

def nodeID(head, dic):
	while head:
		dic[head.data].append(id(head))
		head = head.next

def printList(head, dic):
	while head:
		if id(head) not in dic[head.data]:
			print("Do'nt swap data, swap pointer/node")
			return
		print(head.data, end=' ')
		head = head.next
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ll = Llist()
		tail = None
		for nodeData in arr:
			tail = ll.insert(nodeData, tail)
		dic = defaultdict(list)
		nodeID(ll.head, dic)
		resHead = quickSort(ll.head)
		printList(resHead, dic)
		print()


def quickSort(head):
	if head is None:
		return None
	(h, t) = mysort(head)
	t.next = None
	return h

def mysort(head):
	if head is None:
		return (None, None)
	if head and head.next is None:
		return (head, head)
	left = None
	pleft = None
	right = None
	pright = None
	phead = head
	p = head.next
	while p:
		if p.data < head.data:
			if left is None:
				left = p
				pleft = p
				p = p.next
				pleft.next = None
			else:
				pleft.next = p
				pleft = p
				p = p.next
				pleft.next = None
		elif p.data > head.data:
			if right is None:
				right = p
				pright = p
				p = p.next
				pright.next = None
			else:
				pright.next = p
				pright = p
				p = p.next
				pright.next = None
		elif p.data == head.data:
			phead.next = p
			phead = p
			p = p.next
			phead.next = None
	(lhead, ltail) = mysort(left)
	(rhead, rtail) = mysort(right)
	if lhead is None and rhead is None:
		return (head, phead)
	if lhead is None and rhead is not None:
		phead.next = rhead
		return (head, rtail)
	elif lhead and rhead is None:
		ltail.next = head
		return (lhead, phead)
	elif lhead and rhead:
		ltail.next = head
		phead.next = rhead
		return (lhead, rtail)
from collections import defaultdict

class Node:

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

class Llist:

	def __init__(self):
		self.head = None

	def insert(self, data, tail):
		node = Node(data)
		if not self.head:
			self.head = node
			return node
		tail.next = node
		return node

def nodeID(head, dic):
	while head:
		dic[head.data].append(id(head))
		head = head.next

def printList(head, dic):
	while head:
		if id(head) not in dic[head.data]:
			print("Do'nt swap data, swap pointer/node")
			return
		print(head.data, end=' ')
		head = head.next
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ll = Llist()
		tail = None
		for nodeData in arr:
			tail = ll.insert(nodeData, tail)
		dic = defaultdict(list)
		nodeID(ll.head, dic)
		resHead = quickSort(ll.head)
		printList(resHead, dic)
		print()


def quickSort(head):
	if head == None or head.next == 0:
		return head
	(pivot, curr) = (head, head.next)
	smallhead = small = Node(-1)
	largehead = large = Node(-1)
	while curr:
		if curr == pivot:
			curr = curr.next
		elif curr.data < pivot.data:
			small.next = curr
			curr = curr.next
			small = small.next
		else:
			large.next = curr
			curr = curr.next
			large = large.next
	small.next = None
	large.next = None
	small = quickSort(smallhead.next)
	pivot.next = None
	large = quickSort(largehead.next)
	tmp = small
	while tmp and tmp.next:
		tmp = tmp.next
	if tmp:
		tmp.next = pivot
	else:
		small = pivot
	pivot.next = large
	return small


def swap(temp1, temp2):
	n1 = temp1.data
	temp1.data = temp2.data
	temp2.data = n1

def partition(key, left, right):
	pivot_prev = left
	curr = left
	while left != right:
		if left.data <= key.data:
			pivot_prev = curr
			swap(left, curr)
			curr = curr.next
		left = left.next
	swap(curr, key)
	return pivot_prev

def sort(start, end):
	if start == None or start == end or start == end.next:
		return
	pivot_prev = partition(end, start, end)
	sort(start, pivot_prev)
	if pivot_prev != None and pivot_prev != start:
		sort(pivot_prev.next, end)
	elif pivot_prev != None and pivot_prev.next != None:
		sort(pivot_prev.next.next, end)

def quickSort(head):
	if not head or not head.next:
		return head
	pivot = head
	smallhead = small = Node(-1)
	largehead = large = Node(-1)
	curr = head.next
	while curr:
		if curr == pivot:
			curr = curr.next
		elif curr.data < pivot.data:
			small.next = curr
			curr = curr.next
			small = small.next
		else:
			large.next = curr
			curr = curr.next
			large = large.next
	small.next = None
	large.next = None
	small = quickSort(smallhead.next)
	pivot.next = None
	large = quickSort(largehead.next)
	temp = small
	while temp and temp.next:
		temp = temp.next
	if temp:
		temp.next = pivot
	else:
		small = pivot
	pivot.next = large
	return small