Given a Linked list, rearrange it such that converted list should be of the form a < b > c < d > e < f .. where a, b, c are consecutive data node of linked list and such that the order of linked list is sustained.
For example: In 11 15 20 5 10 we consider only 11 20 5 15 10 because it satisfies the above condition and the order of linked list. 5 20 11 15 10 is not considered as it does not follow the order of linked list.
To maintain the order, keep swapping the adjacent nodes of the linked list (whenever required) to get the desired output.  
Example 1:
Input:
LinkedList: 1->2->3->4 
Output: 1 3 2 4
Example 2:
Input:
LinkedList: 11->15->20->5->10
Output: 11 20 5 15 10
Explanation: In the given linked list,
after arranging them as 11 < 20 > 5
< 15 > 10 in the pattern as asked above.
Your Task:
The task is to complete the function zigZag() which should reorder the list as required and return the head of the linked list.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= size of linked list(a) <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3


'''
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
'''
class Solution:
    def zigzag(self, head_node):
        # Complete this function

Solutions:
class Solution:

	def zigzag(self, head_node):
		count = 1
		curr = head_node
		while curr != None:
			if curr.next != None:
				if count % 2 != 0:
					if curr.data > curr.next.data:
						(curr.data, curr.next.data) = (curr.next.data, curr.data)
					count += 1
				else:
					if curr.data < curr.next.data:
						(curr.data, curr.next.data) = (curr.next.data, curr.data)
					count += 1
			curr = curr.next
		return head_node


class Solution:

	def zigzag(self, head):
		if head:
			temp = head
			c = 0
			while temp.next:
				if c % 2 == 0:
					if temp.data > temp.next.data:
						a = temp.data
						temp.data = temp.next.data
						temp.next.data = a
				elif temp.data < temp.next.data:
					a = temp.data
					temp.data = temp.next.data
					temp.next.data = a
				c += 1
				temp = temp.next
			return head


class Solution:

	def zigzag(self, head_node):
		t = head_node
		c = 0
		while t.next:
			if c % 2 == 0:
				if t.data > t.next.data:
					a = t.data
					t.data = t.next.data
					t.next.data = a
			elif t.data < t.next.data:
				a = t.data
				t.data = t.next.data
				t.next.data = a
			c += 1
			t = t.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		if not head_node or not head_node.next:
			return head_node
		temp = head_node
		flag = True
		while temp and temp.next:
			if flag:
				if temp.data > temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
				else:
					pass
				temp = temp.next
				flag = not flag
			else:
				if temp.data < temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
				else:
					pass
				temp = temp.next
				flag = not flag
		return head_node


class Solution:

	def zigzag(self, head_node):

		def swap(a, b):
			temp = a.data
			a.data = b.data
			b.data = temp
		head = head_node
		curr = head.next
		while head and curr:
			nex = curr.next
			if head.data > curr.data:
				swap(head, curr)
			if nex:
				if nex.data > curr.data:
					swap(nex, curr)
			head = nex
			if head:
				curr = head.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		flag = True
		cur = head_node
		while cur.next != None:
			if flag:
				if cur.data > cur.next.data:
					t = cur.data
					cur.data = cur.next.data
					cur.next.data = t
			elif cur.data < cur.next.data:
				t = cur.data
				cur.data = cur.next.data
				cur.next.data = t
			cur = cur.next
			if flag:
				flag = False
			else:
				flag = True
		return head_node


class Solution:

	def zigzag(self, head):
		tmp = head
		i = 0
		while head and head.next:
			if not i % 2:
				if head.data > head.next.data:
					(head.data, head.next.data) = (head.next.data, head.data)
			elif head.data < head.next.data:
				(head.data, head.next.data) = (head.next.data, head.data)
			i += 1
			head = head.next
		return tmp


class Solution:

	def zigzag(self, head):
		flag = True
		current = head
		while current.next != None:
			if flag:
				if current.data > current.next.data:
					t = current.data
					current.data = current.next.data
					current.next.data = t
			elif current.data < current.next.data:
				t = current.data
				current.data = current.next.data
				current.next.data = t
			current = current.next
			if flag:
				flag = False
			else:
				flag = True
		return head


class Solution:

	def zigzag(self, head_node):
		temp = head_node
		counter = 0
		while temp:
			if temp.next == None:
				return head_node
			if counter % 2 == 0:
				if temp.data < temp.next.data:
					temp = temp.next
				else:
					currData = temp.data
					temp.data = temp.next.data
					temp.next.data = currData
					temp = temp.next
			elif temp.data > temp.next.data:
				temp = temp.next
			else:
				currData = temp.data
				temp.data = temp.next.data
				temp.next.data = currData
				temp = temp.next
			counter += 1


class Solution:

	def zigzag(self, head_node):
		temp = head_node
		flag = True
		while temp.next:
			if flag:
				if temp.data > temp.next.data:
					t = temp.data
					temp.data = temp.next.data
					temp.next.data = t
				flag = False
			else:
				if temp.data < temp.next.data:
					t = temp.data
					temp.data = temp.next.data
					temp.next.data = t
				flag = True
			temp = temp.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		curr = head_node
		flag = True
		while curr.next:
			if flag:
				if curr.data > curr.next.data:
					(curr.data, curr.next.data) = (curr.next.data, curr.data)
				else:
					pass
				flag = not flag
			else:
				if curr.data < curr.next.data:
					(curr.data, curr.next.data) = (curr.next.data, curr.data)
				else:
					pass
				flag = not flag
			curr = curr.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		b = []
		tmp = head_node
		while tmp:
			b.append(tmp.data)
			tmp = tmp.next
		flag = 1
		for i in range(len(b) - 1):
			if flag:
				if b[i] > b[i + 1]:
					(b[i], b[i + 1]) = (b[i + 1], b[i])
			elif b[i] < b[i + 1]:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
			flag = not flag
		tmp = head_node
		for i in b:
			tmp.data = i
			tmp = tmp.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		cur = head_node
		i = -1
		while cur.next:
			i += 1
			if i % 2 != 0:
				if cur.data < cur.next.data:
					(cur.data, cur.next.data) = (cur.next.data, cur.data)
			elif cur.data > cur.next.data:
				(cur.data, cur.next.data) = (cur.next.data, cur.data)
			cur = cur.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		flag = True
		curr = head_node
		while curr.next:
			if flag:
				if curr.data > curr.next.data:
					(curr.data, curr.next.data) = (curr.next.data, curr.data)
			elif curr.data < curr.next.data:
				(curr.data, curr.next.data) = (curr.next.data, curr.data)
			curr = curr.next
			if flag:
				flag = False
			else:
				flag = True
		return head_node


class Solution:

	def zigzag(self, head_node):
		a = head_node
		t = True
		while a.next:
			if t:
				if a.data > a.next.data:
					(a.data, a.next.data) = (a.next.data, a.data)
				t = False
			else:
				if a.data < a.next.data:
					(a.data, a.next.data) = (a.next.data, a.data)
				t = True
			a = a.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		itr = head_node
		flag = True
		while itr.next != None:
			if flag:
				if itr.data > itr.next.data:
					temp = itr.data
					itr.data = itr.next.data
					itr.next.data = temp
			elif itr.data < itr.next.data:
				temp = itr.data
				itr.data = itr.next.data
				itr.next.data = temp
			itr = itr.next
			flag = not flag
		return head_node


class Solution:

	def zigzag(self, head_node):
		curr = head_node
		preflag = 1
		dummy = Node(None)
		dummy.next = curr
		prev = dummy
		while curr.next:
			nxt = curr.next
			if curr.data < nxt.data and preflag == 0 or (curr.data > nxt.data and preflag == 1):
				curr.next = nxt.next
				prev.next = nxt
				nxt.next = curr
				prev = nxt
			else:
				prev = curr
				curr = nxt
			preflag = 0 if preflag == 1 else 1
		return dummy.next


class Solution:

	def zigzag(self, head_node):
		greater = True
		prev = Node(0)
		prev.next = head_node
		dummy = Node(0)
		dummy.next = prev
		cur = head_node
		while cur.next:
			if greater:
				if cur.data > cur.next.data:
					temp = cur.next
					cur.next = temp.next
					temp.next = cur
					prev.next = temp
					prev = temp
				else:
					prev = cur
					cur = cur.next
			elif cur.data < cur.next.data:
				temp = cur.next
				cur.next = temp.next
				temp.next = cur
				prev.next = temp
				prev = temp
			else:
				prev = cur
				cur = cur.next
			greater = not greater
		return dummy.next.next


class Solution:

	def zigzag(self, head_node):
		head = head_node
		while True:
			if head.next == None:
				return head_node
			if head.next.data < head.data:
				(head.data, head.next.data) = (head.next.data, head.data)
			head = head.next
			if head.next == None:
				return head_node
			if head.next.data > head.data:
				(head.data, head.next.data) = (head.next.data, head.data)
			head = head.next


class Solution:

	def zigzag(self, head_node):
		if head_node is None or head_node.next is None:
			return head_node
		cur = head_node
		flag = True
		while cur.next:
			if flag == True:
				if cur.data > cur.next.data:
					(cur.data, cur.next.data) = (cur.next.data, cur.data)
				flag = not flag
			else:
				if cur.data < cur.next.data:
					(cur.data, cur.next.data) = (cur.next.data, cur.data)
				flag = not flag
			cur = cur.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		temp = head_node
		flag = True
		while temp.next is not None:
			if flag:
				if temp.data > temp.next.data:
					store = temp.data
					temp.data = temp.next.data
					temp.next.data = store
			elif temp.data < temp.next.data:
				store = temp.data
				temp.data = temp.next.data
				temp.next.data = store
			temp = temp.next
			if flag:
				flag = False
			else:
				flag = True
		return head_node


class Solution:

	def zigzag(self, head_node):
		flag = True
		cur = head_node
		while cur and cur.next:
			if flag:
				if cur.data > cur.next.data:
					(cur.data, cur.next.data) = (cur.next.data, cur.data)
			elif cur.data < cur.next.data:
				(cur.data, cur.next.data) = (cur.next.data, cur.data)
			cur = cur.next
			flag = not flag
		return head_node


class Solution:

	def zigzag(self, head):
		primenode = head
		trackgreater = False
		while head.next != None:
			if trackgreater:
				if head.data < head.next.data:
					(head.data, head.next.data) = (head.next.data, head.data)
			elif head.data > head.next.data:
				(head.data, head.next.data) = (head.next.data, head.data)
			trackgreater = not trackgreater
			head = head.next
		return primenode


class Solution:

	def zigzag(self, head_node):
		flag = True
		curr = head_node
		while curr.next:
			if flag:
				if curr.data > curr.next.data:
					(curr.data, curr.next.data) = (curr.next.data, curr.data)
			elif curr.data < curr.next.data:
				(curr.data, curr.next.data) = (curr.next.data, curr.data)
			curr = curr.next
			flag = not flag
		return head_node


class Solution:

	def zigzag(self, head_node):
		head = head_node
		tmpHead = head_node
		count = 0
		while tmpHead.next:
			if count % 2:
				if tmpHead.data < tmpHead.next.data:
					(tmpHead.data, tmpHead.next.data) = (tmpHead.next.data, tmpHead.data)
			elif tmpHead.data > tmpHead.next.data:
				(tmpHead.data, tmpHead.next.data) = (tmpHead.next.data, tmpHead.data)
			tmpHead = tmpHead.next
			count += 1
		return head


class Solution:

	def zigzag(self, head_node):
		curr = head_node
		c = 0
		while curr.next:
			if c % 2 == 0:
				if curr.data > curr.next.data:
					(curr.data, curr.next.data) = (curr.next.data, curr.data)
			elif curr.data < curr.next.data:
				(curr.data, curr.next.data) = (curr.next.data, curr.data)
			c += 1
			curr = curr.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		flag = 0
		prev = head_node
		curr = prev.next
		while curr:
			if flag == 0:
				if prev.data > curr.data:
					tmpData = curr.data
					curr.data = prev.data
					prev.data = tmpData
				flag = 1
			else:
				if prev.data < curr.data:
					tmpData = curr.data
					curr.data = prev.data
					prev.data = tmpData
				flag = 0
			prev = curr
			curr = curr.next
		return head_node


class Solution:

	def zigzag(self, head):
		if not head:
			return head
		curr = head
		flag = True
		while curr.next:
			if flag:
				if curr.data > curr.next.data:
					t = curr.data
					curr.data = curr.next.data
					curr.next.data = t
			elif curr.data < curr.next.data:
				t = curr.data
				curr.data = curr.next.data
				curr.next.data = t
			curr = curr.next
			if flag:
				flag = False
			else:
				flag = True
		return head
		return head


class Solution:

	def zigzag(self, head_node):
		l = ['<', '>']
		ptr = head_node
		x = 0
		while ptr.next != None:
			if x > 1:
				x = 0
			curr = ptr.data
			nex = ptr.next.data
			if l[x] == '<':
				if curr > nex:
					tem = curr
					ptr.data = nex
					ptr.next.data = tem
			elif curr < nex:
				tem = curr
				ptr.data = nex
				ptr.next.data = tem
			x += 1
			ptr = ptr.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		i = 0
		node = head_node
		while node and node.next:
			if i % 2 == 0:
				if node.data > node.next.data:
					(node.data, node.next.data) = (node.next.data, node.data)
			elif node.data < node.next.data:
				(node.data, node.next.data) = (node.next.data, node.data)
			node = node.next
			i += 1
		return head_node


class Solution:

	def zigzag(self, head_node):
		flag = True
		curr_node = head_node
		while curr_node.next is not None:
			if flag:
				if curr_node.data > curr_node.next.data:
					(curr_node.data, curr_node.next.data) = (curr_node.next.data, curr_node.data)
			elif curr_node.data < curr_node.next.data:
				(curr_node.data, curr_node.next.data) = (curr_node.next.data, curr_node.data)
			curr_node = curr_node.next
			flag = not flag
		return head_node


class Solution:

	def zigzag(self, head_node):
		temp = head_node
		flag = 0
		while temp.next:
			if not flag:
				if temp.data > temp.next.data:
					var = temp.data
					temp.data = temp.next.data
					temp.next.data = var
			elif temp.data < temp.next.data:
				var = temp.data
				temp.data = temp.next.data
				temp.next.data = var
			if flag:
				flag = 0
			else:
				flag = 1
			temp = temp.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		if not head_node.next:
			return head_node
		previous = None
		pointer = head_node
		if pointer.data > pointer.next.data:
			temp = pointer.next.next
			head_node = pointer.next
			pointer.next = temp
			head_node.next = pointer
		else:
			pointer = pointer.next
		previous = head_node
		op = 1
		while pointer.next:
			if op % 2 == 0:
				if pointer.data > pointer.next.data:
					temp = pointer.next.next
					previous.next = pointer.next
					previous.next.next = pointer
					pointer.next = temp
				else:
					pointer = pointer.next
				previous = previous.next
				op += 1
			elif op % 2 != 0:
				if pointer.data < pointer.next.data:
					temp = pointer.next.next
					previous.next = pointer.next
					previous.next.next = pointer
					pointer.next = temp
				else:
					pointer = pointer.next
				previous = previous.next
				op += 1
		return head_node


class Solution:

	def zigzag(self, head):
		flg = 1
		h = head
		while h.next:
			if flg:
				if h.data > h.next.data:
					(h.data, h.next.data) = (h.next.data, h.data)
			elif h.data < h.next.data:
				(h.data, h.next.data) = (h.next.data, h.data)
			h = h.next
			flg = 1 - flg
		return head


class Solution:

	def zigzag(self, head_node):
		curr = head_node
		flag = 1
		while curr.next != None:
			if flag:
				if curr.data > curr.next.data:
					(curr.data, curr.next.data) = (curr.next.data, curr.data)
			elif curr.data < curr.next.data:
				(curr.data, curr.next.data) = (curr.next.data, curr.data)
			curr = curr.next
			flag = 1 - flag
		return head_node


class Solution:

	def zigzag(self, head_node):
		c = 0
		p = head_node
		while p.next:
			c += 1
			if c % 2 != 0 and p.data > p.next.data:
				(p.data, p.next.data) = (p.next.data, p.data)
			elif c % 2 == 0 and p.data < p.next.data:
				(p.data, p.next.data) = (p.next.data, p.data)
			p = p.next
		return head_node


class Solution:

	def zigzag(self, head):
		i = 0
		temp = head
		while temp is not None:
			if i % 2 == 0:
				if temp.next is not None:
					if temp.data > temp.next.data:
						flag = temp.data
						temp.data = temp.next.data
						temp.next.data = flag
			elif temp.next is not None:
				if temp.data < temp.next.data:
					flag = temp.data
					temp.data = temp.next.data
					temp.next.data = flag
			i += 1
			temp = temp.next
		return head


class Solution:

	def zigzag(self, head_node):
		prev = None
		ans = curr = head_node
		t = True
		while curr.next != None:
			if t:
				if curr.data > curr.next.data:
					temp = curr.data
					curr.data = curr.next.data
					curr.next.data = temp
			elif curr.data < curr.next.data:
				temp = curr.data
				curr.data = curr.next.data
				curr.next.data = temp
			curr = curr.next
			t = not t
		return ans


class Node:

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

class Solution:

	def zigzag(self, head_node):
		h = head_node
		i = 0
		while h.next != None:
			if i % 2:
				if h.data < h.next.data:
					(h.data, h.next.data) = (h.next.data, h.data)
			elif h.data > h.next.data:
				(h.data, h.next.data) = (h.next.data, h.data)
			i += 1
			h = h.next
		return head_node


class Solution:

	def zigzag(self, head):
		flag = 1
		dup = head
		while head.next:
			if flag:
				if head.data > head.next.data:
					(head.data, head.next.data) = (head.next.data, head.data)
			elif head.data < head.next.data:
				(head.data, head.next.data) = (head.next.data, head.data)
			flag = 1 - flag
			head = head.next
		return dup


def swap(node1, node2):
	node1.next = node2.next
	node2.next = node1
	return node2

class Solution:

	def zigzag(self, head_node):
		flag = True
		dummy = Node(-1)
		dummy.next = head_node
		curr = dummy
		while curr and curr.next and curr.next.next:
			if flag:
				if curr.next.data > curr.next.next.data:
					curr.next = swap(curr.next, curr.next.next)
			elif curr.next.data < curr.next.next.data:
				curr.next = swap(curr.next, curr.next.next)
			flag = not flag
			curr = curr.next
		return dummy.next


def comp(n1, n2, n):
	if n == 1:
		return n1.data > n2.data
	else:
		return n1.data < n2.data

class Solution:

	def zigzag(self, head_node):
		h = Node(-1)
		n1 = head_node
		n2 = n1.next
		h.next = n1
		prev = h
		i = 1
		while n1 and n2:
			if comp(n1, n2, i % 2):
				t = n2.next
				n1.next = t
				n2.next = n1
				prev.next = n2
				prev = n2
				n2 = t
			else:
				prev = n1
				n1 = n2
				n2 = n2.next
			i += 1
		return h.next


class Solution:

	def zigzag(self, head_node):
		arr = []
		t = head_node
		while t:
			arr.append(t.data)
			t = t.next
		n = len(arr)
		for i in range(n - 1):
			if i % 2 == 0:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			elif arr[i] < arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		t = head_node
		k = 0
		while t:
			t.data = arr[k]
			k += 1
			t = t.next
		return head_node


class Solution:

	def zigzag(self, head_node):
		if head_node.next == None:
			return head_node
		head = head_node
		count = 0
		while head.next is not None:
			temp = head.next
			if count % 2 == 0:
				if head.data > head.next.data:
					(head.data, head.next.data) = (head.next.data, head.data)
			elif head.data < head.next.data:
				(head.data, head.next.data) = (head.next.data, head.data)
			head = head.next
			count = count + 1
		return head_node


class Solution:

	def zigzag(self, head_node):
		prev = None
		curr = head_node
		nxt = curr.next
		count = 1
		while curr:
			if count % 2 != 0 and nxt:
				if curr.data >= nxt.data:
					a = curr.data
					curr.data = nxt.data
					nxt.data = a
			elif count % 2 == 0 and nxt:
				if curr.data <= nxt.data and nxt:
					a = curr.data
					curr.data = nxt.data
					nxt.data = a
			curr = nxt
			if nxt:
				nxt = nxt.next
			count += 1
		return head_node


class Solution:

	def zigzag(self, head):
		flag = True
		temp = head
		while temp.next:
			if flag:
				if temp.data > temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
				flag = False
			else:
				if temp.data < temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
				flag = True
			temp = temp.next
		return head


class Solution:

	def zigzag(self, head_node):
		start = head_node
		ind = 0
		while head_node and head_node.next:
			swap = False
			if ind % 2 == 0 and head_node.data > head_node.next.data:
				swap = True
			elif ind % 2 != 0 and head_node.data < head_node.next.data:
				swap = True
			if swap:
				(head_node.data, head_node.next.data) = (head_node.next.data, head_node.data)
			ind += 1
			head_node = head_node.next
		return start


class Solution:

	def zigzag(self, head_node):
		head = head_node
		if head.next is None:
			return head
		flag = 1
		current = head
		while current.next:
			if flag:
				if current.data > current.next.data:
					(current.data, current.next.data) = (current.next.data, current.data)
				flag = 0
			else:
				if current.data < current.next.data:
					(current.data, current.next.data) = (current.next.data, current.data)
				flag = 1
			current = current.next
		return head


class Solution:

	def zigzag(self, head):
		temp1 = head
		c = 0
		while temp1.next != None:
			if c % 2 == 0:
				if temp1.data > temp1.next.data:
					(temp1.data, temp1.next.data) = (temp1.next.data, temp1.data)
			elif temp1.data < temp1.next.data:
				(temp1.data, temp1.next.data) = (temp1.next.data, temp1.data)
			temp1 = temp1.next
			c += 1
		return head


class Solution:

	def zigzag(self, head):
		s = head
		l = []
		while s:
			l.append(s.data)
			s = s.next
		for i in range(1, len(l) - 1):
			if i % 2 != 0:
				if l[i - 1] > l[i]:
					(l[i - 1], l[i]) = (l[i], l[i - 1])
				if l[i + 1] > l[i]:
					(l[i + 1], l[i]) = (l[i], l[i + 1])
		if len(l) % 2 == 0:
			if l[-1] < l[-2]:
				(l[-1], l[-2]) = (l[-2], l[-1])
		i = 0
		ss = head
		while ss:
			ss.data = l[i]
			i += 1
			ss = ss.next
		return head


class Solution:

	def zigzag(self, head):
		dummy = Node(0)
		dummy.next = head
		count = 1
		cur = head
		prev = dummy
		while cur.next:
			nxt = cur.next
			if count % 2 != 0:
				if cur.data < nxt.data:
					prev = cur
					cur = nxt
				else:
					cur.next = nxt.next
					nxt.next = cur
					prev.next = nxt
					prev = nxt
			elif cur.data > nxt.data:
				prev = cur
				cur = nxt
			else:
				cur.next = nxt.next
				nxt.next = cur
				prev.next = nxt
				prev = nxt
			count += 1
		return dummy.next


class Solution:

	def zigzag(self, head):
		if head is None or head.next is None:
			return head
		tmp = head
		flag = 1
		while tmp.next:
			if flag:
				if tmp.data < tmp.next.data:
					pass
				else:
					(tmp.data, tmp.next.data) = (tmp.next.data, tmp.data)
				flag = 0
			else:
				if tmp.data > tmp.next.data:
					pass
				else:
					(tmp.data, tmp.next.data) = (tmp.next.data, tmp.data)
				flag = 1
			tmp = tmp.next
		return head


class Solution:

	def zigzag(self, head_node):
		temp = head_node
		c = 0
		while temp.next:
			if c % 2 == 0:
				if temp.data > temp.next.data:
					cur = temp.data
					temp.data = temp.next.data
					temp.next.data = cur
			elif temp.data < temp.next.data:
				cur = temp.data
				temp.data = temp.next.data
				temp.next.data = cur
			temp = temp.next
			c += 1
		return head_node


class Solution:

	def zigzag(self, head_node):
		temp = head_node
		nodes = []
		while temp != None:
			nodes.append(temp)
			temp = temp.next
		for i in range(len(nodes) - 1):
			if i % 2 == 0:
				if nodes[i].data < nodes[i + 1].data:
					continue
				else:
					temp = nodes[i]
					nodes[i] = nodes[i + 1]
					nodes[i + 1] = temp
			elif i % 2 == 1:
				if nodes[i].data > nodes[i + 1].data:
					continue
				else:
					temp = nodes[i]
					nodes[i] = nodes[i + 1]
					nodes[i + 1] = temp
		head = nodes[0]
		for i in range(len(nodes) - 1):
			nodes[i].next = nodes[i + 1]
		nodes[-1].next = None
		return head
import io
import sys

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, new_node):
		if self.head is None:
			self.head = new_node
			self.tail = new_node
			return
		self.tail.next = new_node
		self.tail = self.tail.next

def print_list(head_node):
	curr_node = head_node
	while curr_node is not None:
		print(curr_node.data, end=' ')
		curr_node = curr_node.next
	print()
if __name__ == '__main__':
	for cases in range(int(input())):
		n = int(input())
		nodes = list(map(int, input().strip().split()))
		a = LinkedList()
		for x in nodes:
			a.append(Node(x))
		print_list(Solution().zigzag(a.head))


class Solution:

	def zigzag(self, head_node):
		temp = head_node
		flag = True
		while temp.next != None:
			if flag:
				if temp.data > temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
				flag = False
			else:
				if temp.data < temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
				flag = True
			temp = temp.next
		return head_node
import io
import sys

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, new_node):
		if self.head is None:
			self.head = new_node
			self.tail = new_node
			return
		self.tail.next = new_node
		self.tail = self.tail.next

def print_list(head_node):
	curr_node = head_node
	while curr_node is not None:
		print(curr_node.data, end=' ')
		curr_node = curr_node.next
	print()
if __name__ == '__main__':
	for cases in range(int(input())):
		n = int(input())
		nodes = list(map(int, input().strip().split()))
		a = LinkedList()
		for x in nodes:
			a.append(Node(x))
		print_list(Solution().zigzag(a.head))


class Solution:

	def zigzag(self, head_node):
		temp1 = head_node
		temp2 = head_node.next
		itr = 1
		while temp2 != None:
			if itr % 2 != 0:
				if temp2.data < temp1.data:
					swap = temp1.data
					temp1.data = temp2.data
					temp2.data = swap
			elif temp2.data > temp1.data:
				swap = temp1.data
				temp1.data = temp2.data
				temp2.data = swap
			temp1 = temp1.next
			temp2 = temp2.next
			itr += 1
		return head_node
import io
import sys

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def append(self, new_node):
		if self.head is None:
			self.head = new_node
			self.tail = new_node
			return
		self.tail.next = new_node
		self.tail = self.tail.next

def print_list(head_node):
	curr_node = head_node
	while curr_node is not None:
		print(curr_node.data, end=' ')
		curr_node = curr_node.next
	print()
if __name__ == '__main__':
	for cases in range(int(input())):
		n = int(input())
		nodes = list(map(int, input().strip().split()))
		a = LinkedList()
		for x in nodes:
			a.append(Node(x))
		print_list(Solution().zigzag(a.head))


class Solution:

	def zigzag(self, head_node):
		arr = []
		while head_node:
			arr.append(head_node.data)
			head_node = head_node.next
		for i in range(len(arr) - 1):
			if arr[i] > arr[i + 1] and i % 2 == 0:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			elif arr[i] < arr[i + 1] and i % 2 != 0:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		dummy = Node(0)
		head_node = dummy
		i = 0
		while i < len(arr):
			head_node.next = Node(arr[i])
			i += 1
			head_node = head_node.next
		return dummy.next


class Solution:

	def zigzag(self, head):
		temp = head
		flag = 0
		while temp.next:
			if flag == 0:
				if temp.data > temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
			elif temp.data < temp.next.data:
				(temp.data, temp.next.data) = (temp.next.data, temp.data)
			flag = 1 - flag
			temp = temp.next
		return head


class Solution:

	def zigzag(self, head_node):
		Flag = 1
		curr = head_node
		while curr.next != None:
			if Flag:
				if curr.data > curr.next.data:
					t = curr.data
					curr.data = curr.next.data
					curr.next.data = t
			elif curr.data < curr.next.data:
				t = curr.data
				curr.data = curr.next.data
				curr.next.data = t
			curr = curr.next
			if Flag:
				Flag = 0
			else:
				Flag = 1
		return head_node


class Solution:

	def zigzag(self, head):
		if head is None or head.next is None:
			return head
		temp = head
		c = 0
		while temp.next != None:
			c += 1
			if c % 2 == 0:
				if temp.data < temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
			elif temp.data > temp.next.data:
				(temp.data, temp.next.data) = (temp.next.data, temp.data)
			temp = temp.next
		return head


class Solution:

	def zigzag(self, head_node):
		count = 1
		temp = head_node
		nextt = temp.next
		while temp.next != None:
			if count == 1 or count % 2 == 1:
				if temp.data > nextt.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
			elif temp.data < nextt.data:
				(temp.data, nextt.data) = (nextt.data, temp.data)
			count += 1
			temp = temp.next
			nextt = nextt.next
		return head_node


class Solution:

	def zigzag(self, head):
		if head is None:
			return
		c = head
		big = True
		while c and c.next:
			if big:
				if c.data > c.next.data:
					(c.next.data, c.data) = (c.data, c.next.data)
			elif c.data < c.next.data:
				(c.next.data, c.data) = (c.data, c.next.data)
			c = c.next
			big = not big
		return head