Given a linked list, you have to perform the following task:
	Extract the alternative nodes starting from second node.
	Reverse the extracted list.
	Append the extracted list at the end of the original list.
Ã¢â¬â¹Example 1:
Input:
LinkedList = 10->4->9->1->3->5->9->4
Output: 10 9 3 9 4 5 1 4
Explanation: Reversing the alternative
nodes from the given list, and then
appending them to the end of the list
results in a list with the elements as
10 9 3 9 4 5 1 4.
Ã¢â¬â¹Example 2:
Input:
LinkedList = 1->2->3->4->5
Output: 1 3 5 4 2 
Explanation:
Your Task:
You don't have to read input or print anything. Your task is to complete the function rearrange() which takes the head of the linked list as input and rearranges the list as required.
Note: Try to solve the problem without using any extra memory.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
0 <= Node_value <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: """
  reverse alternate nodes and append at the end
  The input list will have at least one element
  Node is defined as
class Node:

	# Constructor to initialize the node object
	def __init__(self, data):
		self.data = data
		self.next = None

"""
class Solution:
    def rearrange(self, head):
        # Code here

Solutions:
class Solution:

	def rearrange(self, head):
		l = []
		le = []
		lo = []
		temp1 = head
		temp2 = head
		while temp1:
			l.append(temp1.data)
			temp1 = temp1.next
		for i in range(len(l)):
			if i % 2 == 0:
				le.append(l[i])
			else:
				lo.append(l[i])
		lo.reverse()
		final = le + lo
		for item in final:
			temp2.data = item
			temp2 = temp2.next
		return head


class Solution:

	def rearrange(self, head):
		odd = head
		even = head.next
		dummy = None
		while odd and even:
			temp = even.next
			odd.next = temp
			prev = odd
			odd = temp
			even.next = dummy
			dummy = even
			if odd != None:
				even = odd.next
		if even == None and odd != None:
			odd.next = dummy
		else:
			prev.next = dummy
		return head


class Solution:

	def rearrange(self, head):

		def reverse(cur):
			prev = None
			while cur:
				next = cur.next
				cur.next = prev
				prev = cur
				cur = next
			return prev
		if not head or not head.next:
			return head
		odd = head
		even = head.next
		head2 = even
		while odd.next and even.next:
			odd.next = even.next
			odd = odd.next
			even.next = odd.next
			even = even.next
		head2 = reverse(head2)
		odd.next = head2
		return head2


class Solution:

	def rearrange(self, head):
		l = []
		a1 = []
		a2 = []
		temp1 = head
		temp2 = head
		while temp1:
			l.append(temp1.data)
			temp1 = temp1.next
		for i in range(len(l)):
			if i % 2 == 0:
				a1.append(l[i])
			else:
				a2.append(l[i])
		a2.reverse()
		res = a1 + a2
		for j in res:
			temp2.data = j
			temp2 = temp2.next
		return head


class Solution:

	def rearrange(self, head):
		if head is None or head.next is None or head.next.next is None:
			return head
		fir = None
		fh = None
		sec = None
		sh = None
		tmp = head
		while tmp and tmp.next:
			if not fh:
				fh = tmp
				sh = tmp.next
				fir = fh
				sec = sh
			else:
				fir.next = tmp
				fir = fir.next
				sec.next = tmp.next
				sec = sec.next
			tmp = tmp.next.next
		if tmp:
			fir.next = tmp
			fir = fir.next
			sec.next = None
		else:
			fir.next = None
		prev = None
		curr = sh
		while curr:
			nx = curr.next
			curr.next = prev
			prev = curr
			curr = nx
		fir.next = prev
		return fh


class Solution:

	def rearrange(self, head):
		l = []
		o = []
		e = []
		temp = head
		temp2 = head
		while temp:
			l.append(temp.data)
			temp = temp.next
		for i in range(len(l)):
			if i % 2 == 0:
				e.append(l[i])
			else:
				o.append(l[i])
		o.reverse()
		final = e + o
		for item in final:
			temp2.data = item
			temp2 = temp2.next
		return head


class Solution:

	def collect(self, head):
		temp = head.next
		nhead = None
		rhead = None
		count = 0
		while temp:
			if count == 0:
				node = temp
				temp = temp.next
				node.next = None
				if nhead == None:
					nhead = node
				else:
					node.next = nhead
					nhead = node
				count = 1
			else:
				node = temp
				temp = temp.next
				node.next = None
				if rhead == None:
					rhead = node
					rtemp = rhead
				else:
					rtemp.next = node
					rtemp = rtemp.next
				count = 0
		return (nhead, rhead)

	def rearrange(self, head):
		temp = head
		flag = 0
		count = 0
		while temp != None:
			count += 1
			if count > 2:
				flag = 1
				break
			temp = temp.next
		if flag == 0:
			return
		(nhead, rhead) = self.collect(head)
		temp = rhead
		while temp.next != None:
			temp = temp.next
		temp.next = nhead
		head.next = rhead


class Solution:

	def rearrange(self, head):
		prev = None
		p = head
		while p:
			n = p.next
			if not n:
				break
			p.next = n.next
			n.next = prev
			prev = n
			if not p.next:
				break
			p = p.next
		p.next = prev
		return head


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

class Solution:

	def rearrange(self, head):
		if not head.next:
			return head
		temp1 = temp2 = None
		tmp1 = tmp2 = None
		while head and head.next:
			if not temp1:
				temp1 = head
				tmp1 = head
			else:
				temp1.next = head
				temp1 = temp1.next
			if not temp2:
				temp2 = head.next
				tmp2 = head.next
			else:
				temp2.next = head.next
				temp2 = temp2.next
			head = head.next.next
		temp2 = None
		tmp2 = reverse(tmp2)
		temp1.next = tmp2
		return tmp1


class Solution:

	def rearrange(self, head):
		li = []
		even = []
		odd = []
		temp1 = head
		temp2 = head
		while temp1:
			li.append(temp1.data)
			temp1 = temp1.next
		for i in range(len(li)):
			if i % 2 == 0:
				even.append(li[i])
			else:
				odd.append(li[i])
		odd.reverse()
		final = even + odd
		for i in final:
			temp2.data = i
			temp2 = temp2.next
		return head


class Solution:

	def reverseLL(self, head):
		new_head = None
		while head != None:
			store = head.next
			head.next = new_head
			new_head = head
			head = store
		return new_head

	def rearrange(self, head):
		if head == None:
			return None
		oh = head
		ot = head
		eh = head.next
		et = head.next
		while et != None and et.next != None:
			ot.next = ot.next.next
			ot = ot.next
			if et.next != None:
				et.next = et.next.next
				et = et.next
		eh = self.reverseLL(eh)
		ot.next = eh
		return head


class Solution:

	def findTail(self, head):
		tail = head
		while tail and tail.next:
			tail = tail.next
		return tail

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

	def rearrange(self, head):
		if head == None or head.next == None:
			return head
		dum1 = temp1 = head
		dum2 = temp2 = head.next
		while temp2 and temp1:
			temp1.next = temp2.next
			temp1 = temp1.next
			if temp1:
				temp2.next = temp1.next
				temp2 = temp2.next
		dum2 = self.reverse(dum2)
		tdum1 = self.findTail(dum1)
		tdum1.next = dum2
		return dum1.next


class Solution:

	def rearrange(self, head):
		p = head
		count = 1
		while p.next is not None:
			count += 1
			p = p.next
		if count <= 2:
			return
		q = head
		p = head.next
		new = None
		if count % 2 == 0:
			count = int(count / 2) - 1
		else:
			count = int(count / 2)
		while count != 0:
			q.next = p.next
			if new is None:
				new = p
				p.next = None
			else:
				p.next = new
				new = p
			q = q.next
			p = q.next
			count -= 1
		if q.next is not None:
			q = q.next
		q.next = new


class Solution:

	def rearrange(self, head):
		h = head
		j = head.next
		k = head.next
		while h.next and j:
			h.next = j.next
			if j.next:
				h = h.next
			j.next = h.next
			j = j.next
		prev = None
		while k:
			temp = k.next
			k.next = prev
			prev = k
			k = temp
		h.next = prev
		return head


class Solution:

	def reverse(self, head):
		prev = None
		while head != None:
			nxt = head.next
			head.next = prev
			prev = head
			head = nxt
		return prev

	def rearrange(self, head):
		if head == None:
			return head
		l1 = head
		if head.next == None:
			return head
		l2 = head.next
		curr = head
		while curr != None and curr.next != None:
			nxt = curr.next
			curr.next = curr.next.next
			curr = nxt
		l2 = self.reverse(l2)
		curr = l1
		prev = None
		while curr != None:
			prev = curr
			curr = curr.next
		prev.next = l2
		return l1


class Solution:

	def rearrange(self, head):
		start = head
		temp2 = None
		while head and head.next and head.next.next:
			temp1 = head.next
			head.next = head.next.next
			temp1.next = temp2
			head = head.next
			temp2 = temp1
		if head.next is None:
			head.next = temp2
		else:
			head.next.next = head.next
			head.next.next = temp2
		return start


class Solution:

	def rearrange(self, head):
		h1 = Node(None)
		temp = head
		if temp is None or temp.next is None or temp.next.next is None:
			return head
		while temp.next:
			alt = temp.next
			if temp.next.next is not None:
				temp.next = alt.next
				temp = temp.next
			else:
				temp.next = None
			node = Node(alt.data)
			if h1.data is None:
				h1 = node
			else:
				node.next = h1
				h1 = node
		temp = head
		while temp.next:
			temp = temp.next
		temp.next = h1
		return head


class Solution:

	def rearrange(self, head):

		def reverse(head):
			prev = None
			cur = head
			while cur:
				nxt = cur.next
				cur.next = prev
				prev = cur
				cur = nxt
			return prev
		cur = head
		even = None
		odd = None
		c = 0
		if head.next == None:
			return head
		while cur:
			c += 1
			if c % 2 == 0:
				if even == None:
					even = cur
					evenp = even
				else:
					even.next = cur
					even = even.next
			elif odd == None:
				odd = cur
				oddp = odd
			else:
				odd.next = cur
				odd = odd.next
			cur = cur.next
		even.next = None
		even = reverse(evenp)
		odd.next = even
		return oddp


class Solution:

	def rearrange(self, head):
		ch = head
		arr = [[], []]
		i = 0
		while head != None:
			arr[i].append(head.data)
			head = head.next
			i ^= 1
		arr[-1].reverse()
		arr = arr[0] + arr[1]
		copy = ch
		for x in arr:
			copy.data = x
			copy = copy.next
		return ch


class Solution:

	def rearrange(self, head):
		curr = head
		even = []
		odd = []
		i = 0
		while curr:
			if i % 2 == 0:
				even.append(curr.data)
			else:
				odd.append(curr.data)
			curr = curr.next
			i += 1
		even = even + odd[::-1]
		curr = head
		for i in even:
			curr.data = i
			curr = curr.next


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

class Solution:

	def rearrange(self, head):
		p = head
		p.prev = None
		while p.next:
			nxt = p.next
			nxt.prev = p
			p = nxt
		tail = p
		p = head
		myll = Node(None)
		val = myll
		last = False
		while p:
			if p == tail:
				last = True
			myll.next = p
			myll = myll.next
			if p.next and p.next.next:
				p = p.next.next
			else:
				myll.next = None
				break
		if last:
			tail = tail.prev
		while tail:
			myll.next = tail
			myll = myll.next
			if tail.prev and tail.prev.prev:
				tail = tail.prev.prev
			else:
				myll.next = None
				break
		return val.next


class Solution:

	def rearrange(self, head):
		values = list()
		temp1 = temp2 = head
		while temp1:
			values.append(temp1.data)
			temp1 = temp1.next
		first = values[::2]
		second = values[1::2][::-1]
		ans = first + second
		for i in ans:
			temp2.data = i
			temp2 = temp2.next


class Solution:

	def rearrange(self, head):
		alt = []
		first = []
		temp = head
		j = 1
		while temp:
			if j % 2:
				first.append(temp.data)
			else:
				alt.append(temp.data)
			j += 1
			temp = temp.next
		j = 0
		k = -1
		temp = head
		while temp:
			if j < len(first):
				temp.data = first[j]
				j += 1
			else:
				temp.data = alt[k]
				k -= 1
			temp = temp.next
		return head


class Solution:

	def rearrange(self, head):

		def reverseList(head):
			if head == None or head.next == None:
				return head
			prev = head
			curr = head.next
			prev.next = None
			while curr != None:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
			return prev
		if head == None or head.next == None or head.next.next == None:
			return head
		curr = head
		while curr.next != None:
			curr = curr.next
		tail = curr
		tailCopy = curr
		curr2 = head
		while curr2 != None and curr2.next != None and (curr2.next != tail) and (curr2 != tail):
			alt = curr2.next
			curr2.next = curr2.next.next
			alt.next = None
			tailCopy.next = alt
			tailCopy = tailCopy.next
			curr2 = curr2.next
		if curr2 == None:
			return head
		elif curr2.next == tail:
			alt = curr2.next
			curr2.next = tail.next
			alt.next = None
			tailCopy.next = alt
		curr2.next = reverseList(curr2.next)
		return head


class Solution:

	def rearrange(self, head):
		new = Node(-1)
		alt = Node(-1)
		dummy = alt
		curr = new
		itr = head
		count = 1
		while itr:
			if count % 2 == 0:
				alt.next = itr
				itr = itr.next
				alt = alt.next
				alt.next = None
			else:
				new.next = itr
				itr = itr.next
				new = new.next
				new.next = None
			count += 1
		temp = None
		itr = dummy.next
		while itr:
			next = itr.next
			itr.next = temp
			temp = itr
			itr = next
			dummy.next = temp
		new.next = dummy.next
		return curr.next


class Solution:

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

	def rearrange(self, head):
		if head == None or head.next == None:
			return head
		ptr1 = head
		ptr2 = head.next
		curr1 = ptr1
		curr2 = ptr2
		while curr2 and curr2.next:
			curr1.next = curr1.next.next
			curr1 = curr1.next
			curr2.next = curr2.next.next
			curr2 = curr2.next
		rev = self.reverse(ptr2)
		curr1.next = rev
		return ptr1


class Solution:

	def rearrange(self, head):
		if head.next == None or head.next.next == None:
			return
		last = head
		while last.next != None and last.next.next != None:
			last = last.next.next
		if last.next == None:
			current = last
		else:
			current = last.next
		prev = head
		temp = head.next
		while temp != None:
			prev.next = temp.next
			temp.next = current.next
			current.next = temp
			prev = prev.next
			temp = prev.next
			if prev == last:
				break


class Solution:

	def rearrange(self, head):
		odd = head
		even = None
		while odd and odd.next:
			oldeven = even
			even = odd.next
			if even.next:
				odd.next = even.next
			pr = odd
			odd = even.next
			even.next = oldeven
			if not odd:
				pr.next = even
				break
			elif not odd.next:
				odd.next = even
				break
		return head


class Solution:

	def reverseList(self, head):
		pre = None
		trav = head
		nhead = head
		while trav:
			ele = trav.next
			trav.next = pre
			nhead = trav
			pre = trav
			trav = ele
		return nhead

	def rearrange(self, head):
		k = 1
		pre = None
		pos = None
		nhead = None
		nhead2 = None
		h1 = h2 = head
		while h1:
			if k % 2 == 0:
				if not pre:
					nhead = h1
					pre = h1
				else:
					pre.next = h1
					pre = h1
			elif not pos:
				pos = h1
				nhead2 = h1
			else:
				pos.next = h1
				pos = h1
			k += 1
			h1 = h1.next
			if pos and pos.next:
				pos.next = None
			if pre and pre.next:
				pre.next = None
		if nhead:
			nhead = self.reverseList(nhead)
		if nhead2:
			pos.next = nhead
			return nhead2
		return nhead


class Solution:

	def rearrange(self, head):
		a = []
		b = []
		tmp = head
		tmp1 = head
		while tmp != None:
			a.append(tmp.data)
			if tmp.next == None:
				break
			tmp = tmp.next.next
		while tmp1 != None:
			tmp1 = tmp1.next
			if tmp1 == None:
				break
			b.append(tmp1.data)
			tmp1 = tmp1.next
		tmp = head
		for i in a:
			tmp.data = i
			tmp = tmp.next
		for i in reversed(b):
			tmp.data = i
			tmp = tmp.next
		return head


class Solution:

	def rearrange(self, head):
		if not head or not head.next:
			return head
		root = None
		prev = head
		current = prev.next
		while current and current.next:
			prev.next = current.next
			prev = prev.next
			if not root:
				root = current
				current.next = None
			else:
				current.next = root
				root = current
			current = prev.next
		if current:
			prev = current
		prev.next = root
		return head


class Solution:

	def rearrange(self, head):
		(odd, even) = self.split(head)
		rev_even = self.reverse(even)
		cur = odd
		while cur and cur.next:
			cur = cur.next
		cur.next = rev_even
		return odd

	def reverse(self, head):
		cur = head
		prev = None
		while cur:
			nextNode = cur.next
			cur.next = prev
			prev = cur
			cur = nextNode
		return prev

	def split(self, head):
		odd = Node(-1)
		even = Node(-1)
		cur = head
		o = odd
		e = even
		while cur:
			o.next = cur
			o = o.next
			cur = cur.next
			if cur:
				e.next = cur
				e = e.next
				cur = cur.next
		o.next = None
		e.next = None
		return (odd.next, even.next)


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None:
			return head
		sprev_reverse = None
		fmain = frun = head
		smain = srun = head.next
		holdprev_reverse = smain
		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
				holdprev_reverse.next = sprev_reverse
				sprev_reverse = holdprev_reverse
				holdprev_reverse = srun
		srun.next = None
		holdprev_reverse.next = sprev_reverse
		frun.next = holdprev_reverse
		return fmain


class Solution:

	def rearrange(self, 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 = None
		prevnode = None
		while smain != None:
			holdnode = smain.next
			smain.next = prevnode
			prevnode = smain
			smain = holdnode
		frun.next = prevnode
		return fmain


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None:
			return head
		f_main = f_run = head
		s_main = s_run = head.next
		while f_run.next != None and s_run.next != None:
			f_run.next = f_run.next.next
			f_run = f_run.next
			if s_run.next.next != None:
				s_run.next = s_run.next.next
				s_run = s_run.next
		s_run.next = None
		f_run.next = self.reversed(s_main)
		return f_main

	def reversed(self, node):
		primenode = None
		while node != None:
			holdnode = node.next
			node.next = primenode
			primenode = node
			node = holdnode
		return primenode


class Solution:

	def rearrange(self, head):
		ae = []
		ao = []
		c = 0
		cu = head
		while cu is not None:
			if c % 2 == 0:
				ae.append(cu.data)
			else:
				ao.append(cu.data)
			cu = cu.next
			c += 1
		ao = ao[::-1]
		a = ae + ao
		cur = head
		for i in a:
			cur.data = i
			cur = cur.next
		return cur


class Solution:

	def rearrange(self, head):

		def getReverse(head):
			reverse = None
			while head != None:
				temp = head.next
				head.next = reverse
				reverse = head
				head = temp
			return reverse
		temp = head
		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 = getReverse(result.next)


class Solution:

	def rearrange(self, head):
		temp = head
		p = head.next
		prev = head.next
		while temp.next != None and temp.next.next != None:
			temp.next = prev.next
			temp = temp.next
			prev.next = temp.next
			prev = prev.next
		d = None
		while p != None:
			n = p.next
			p.next = d
			d = p
			p = n
		temp.next = d
		return p


class Solution:

	def rearrange(self, head):
		temp = head
		h = None
		while temp != None and temp.next != None:
			node = temp.next
			temp.next = temp.next.next
			node.next = None
			if h == None:
				h = node
			else:
				node.next = h
				h = node
			prev = temp
			temp = temp.next
		if temp == None:
			prev.next = h
		else:
			temp.next = h
		return head


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None or head.next.next == None:
			return head
		newnode = Node(-1)
		c = newnode
		c.next = head.next
		c = c.next
		temp = head
		while temp.next.next:
			temp.next = temp.next.next
			temp = temp.next
			c.next = temp.next
			c = temp.next
			if temp.next == None:
				break
		temp.next = None
		prev = None
		current = newnode.next
		while current is not None:
			next = current.next
			current.next = prev
			prev = current
			current = next
		newnode.next = prev
		temp.next = newnode.next
		return head


import copy

class Solution:

	def print_ll(self, head):
		res = []
		while head != None:
			res.append(head.data)
			head = head.next
		print(res)

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

	def rearrange(self, head):
		temp = head
		ll = Node(float('inf'))
		ll_head = ll
		while temp != None:
			if temp.next != None:
				ll.data = temp.next.data
				temp.next = temp.next.next
				if temp.next != None and temp.next.next != None:
					ll.next = Node(float('inf'))
					ll = ll.next
			temp = temp.next
		ll = self.reverseList(ll_head)
		if ll.data == float('inf'):
			ll = None
		temp = head
		while temp.next != None:
			temp = temp.next
		temp.next = ll
		return head


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None:
			return head
		newhead = None
		n = head
		while n and n.next:
			if newhead == None:
				node = n.next
				n.next = n.next.next
				prev = node
				newhead = node
				n = n.next
			else:
				node = n.next
				n.next = n.next.next
				prev.next = node
				prev = prev.next
				n = n.next
		prev.next = None
		curr = newhead
		prev = None
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		n = head
		while n.next:
			n = n.next
		n.next = prev


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None:
			return
		curr = head
		second = Node(-1)
		temp = second
		tail = None
		while curr != None:
			tail = curr
			nextt = curr.next
			temp.next = nextt
			temp = nextt
			if nextt != None:
				curr.next = nextt.next
			curr = curr.next
		temp = second.next
		second.next = None
		second = temp
		prev = None
		curr = second
		while curr != None:
			nextt = curr.next
			curr.next = prev
			prev = curr
			curr = nextt
		tail.next = prev


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None:
			return head
		oh = ot = eh = et = None
		i = 0
		curr = head
		while head:
			if i % 2 == 0:
				if eh == None:
					eh = et = head
				else:
					et.next = head
					et = et.next
			elif oh == None:
				oh = ot = head
			else:
				ot.next = head
				ot = ot.next
			head = head.next
			i += 1
		if oh == None:
			return eh
		ot.next = None
		prev = None
		curr = oh
		while curr:
			nex = curr.next
			curr.next = prev
			prev = curr
			curr = nex
		et.next = prev


class Solution:

	def rearrange(self, head):

		def reverse(n):
			curr = n
			pre = None
			while curr:
				nxt = curr.next
				curr.next = pre
				pre = curr
				curr = nxt
			return pre
		(ptr1, ptr2) = (head, Node(0))
		alter = ptr2
		while ptr1 and ptr1.next:
			ptr2.next = ptr1.next
			ptr1.next = ptr1.next.next
			if ptr1.next:
				ptr1 = ptr1.next
			ptr2 = ptr2.next
		ptr2.next = None
		alter = alter.next
		ptr1.next = reverse(alter)
		return head


class Solution:

	def rearrange(self, head):
		odd = head
		even = head.next
		newe = even
		while even != None and even.next != None:
			odd.next = odd.next.next
			even.next = even.next.next
			odd = odd.next
			even = even.next
		a = self.reverse(newe)
		odd.next = a

	def reverse(self, new):
		prev = None
		curr = new
		next = None
		while curr != None:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		self.head = prev
		return prev


class Node:

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

class Solution:

	def rearrange(self, head):
		if head is None or head.next is None:
			return head
		temp = []
		curr = head
		prev = None
		while curr and curr.next:
			temp.append(curr.next.data)
			curr.next = curr.next.next
			prev = curr
			curr = curr.next
		next = curr if curr else prev
		while temp:
			next.next = Node(temp.pop())
			next = next.next


class Solution:

	def rearrange(self, head):
		if head.next == None or head.next.next == None:
			return head
		first = head
		second = head.next
		s1 = Node(0)
		s = s1
		while second:
			first.next = second.next
			second.next = None
			s.next = second
			s = s.next
			if first.next:
				first = first.next
			second = first.next
		s1 = s1.next

		def rev(linkd):
			if linkd == None or linkd.next == None:
				return linkd
			pre = None
			cur = linkd
			nex = linkd.next
			while nex:
				cur.next = pre
				pre = cur
				cur = nex
				nex = nex.next
			cur.next = pre
			return cur
		r = rev(s1)
		first.next = r
		return head


class Solution:

	def rearrange(self, head):
		if not head.next:
			return head
		prev = None
		(odd, even) = (head, head.next)
		prev = None
		while even.next and even.next.next:
			odd.next = even.next
			even.next = prev
			prev = even
			odd = odd.next
			even = odd.next
		if even.next:
			odd.next = even.next
			odd = odd.next
		even.next = prev
		odd.next = even


class Solution:

	def rearrange(self, head):
		if not head.next:
			return head
		(odd, even) = (head, head.next)
		evenfirst = even
		while 1:
			if not (odd and even and even.next):
				prev = None
				cur = evenfirst
				while cur:
					ne = cur.next
					cur.next = prev
					prev = cur
					cur = ne
				odd.next = prev
				break
			odd.next = even.next
			odd = even.next
			even.next = odd.next
			even = odd.next
		return head


class Solution:

	def rearrange(self, head):
		if head.next is None:
			return head
		if head.next.next is None:
			return head
		dummy_odd = Node(None)
		dummy_even = Node(None)
		odd_tail = dummy_odd
		even_tail = dummy_even
		h = head
		i = 1
		while h is not None:
			if i % 2 == 0:
				even_tail.next = h
				even_tail = h
			else:
				odd_tail.next = h
				odd_tail = h
			h = h.next
			i = i + 1
		odd_tail.next = None
		even_tail.next = None
		odd_head = dummy_odd.next
		even_head = dummy_even.next
		curr = even_head
		prev = None
		while curr.next is not None:
			Next = curr.next
			curr.next = prev
			prev = curr
			curr = Next
		curr.next = prev
		even_head = curr
		odd_tail.next = even_head
		return odd_head


class Solution:

	def rearrange(self, h):
		ans = h
		k = h.next
		a = ans
		b = k
		while b and b.next:
			a.next = b.next
			b.next = b.next.next
			a = a.next
			b = b.next
		t = k
		prev = None
		while t:
			x = t.next
			t.next = prev
			prev = t
			t = x
		a.next = prev
		return ans


class Solution:

	def rearrange(self, head):
		count = 0
		temp = head
		while temp:
			temp = temp.next
			count += 1
		if count < 3:
			return
		(curr, k) = (head, 1)
		odd = Node(0)
		even = Node(0)
		(first, second) = (odd, even)
		while curr is not None:
			if k % 2 == 0:
				even.next = curr
				even = even.next
			else:
				odd.next = curr
				odd = odd.next
			curr = curr.next
			k += 1
		prev = None
		tmp = second.next
		while tmp:
			temp4 = tmp.next
			tmp.next = prev
			prev = tmp
			tmp = temp4
		odd.next = even
		return first.next


class Solution:

	def rearrange(self, head):

		def reverse(node):
			prev = None
			curr = node
			while curr:
				nexx = curr.next
				curr.next = prev
				prev = curr
				curr = nexx
			return prev
		head2 = head.next
		curr = head
		rev = head.next
		while curr and curr.next:
			curr.next = curr.next.next
			curr = curr.next
			if rev.next:
				rev.next = rev.next.next
				rev = rev.next
		temp1 = head
		while temp1:
			prev = temp1
			temp1 = temp1.next
		prev.next = reverse(head2)
		return head


class Solution:

	def rearrange(self, head):
		curr = head
		i = 0
		a = []
		b = []
		while curr:
			if i % 2 == 0:
				a.append(curr.data)
			else:
				b.append(curr.data)
			i += 1
			curr = curr.next
		a = a + b[::-1]
		temp = head
		head = temp
		i = 0
		while temp:
			temp.data = a[i]
			i += 1
			temp = temp.next
		return head


class Solution:

	def rearrange(self, head):
		if not head or not head.next or (not head.next.next):
			return head
		odd = head
		even = odd.next
		odd.next = odd.next.next
		odd = odd.next
		even.next = None
		while odd.next:
			temp = odd.next.next
			odd.next.next = even
			even = odd.next
			odd.next = temp
			if temp:
				odd = temp
		odd.next = even
		return head


class Solution:

	def rearrange(self, head):
		n = head
		tail = None
		while True:
			if not n.next or not n.next.next:
				break
			temp = n.next
			n.next = temp.next
			temp.next = tail
			tail = temp
			n = n.next
		if n.next:
			n = n.next
		n.next = tail


class Solution:

	def rearrange(self, head):
		oddHead = odd = Node(0)
		evenHead = even = Node(0)
		i = 1
		while head:
			if i % 2 == 0:
				even.next = head
				even = even.next
			else:
				odd.next = head
				odd = odd.next
			head = head.next
			i += 1
		even.next = None
		res = self.reverse(evenHead.next)
		odd.next = res
		return oddHead.next

	def reverse(self, head):
		curr = temp = head
		prev = None
		while curr:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		return prev


class Solution:

	def rev(self, h):
		cur = h
		prev = None
		while cur:
			n = cur.next
			cur.next = prev
			prev = cur
			cur = n
		return prev

	def rearrange(self, head):
		c = 0
		cur = head
		first = Node(0)
		f1 = first
		sec = Node(0)
		s1 = sec
		while cur:
			if c % 2 == 0:
				first.next = cur
				first = cur
			else:
				sec.next = cur
				sec = cur
			cur = cur.next
			c += 1
		first.next = None
		sec.next = None
		s1 = self.rev(s1.next)
		first.next = s1
		return f1


class Solution:

	def rearrange(self, head):

		def reverse(head):
			prev = None
			curr = head
			while curr:
				nxt = curr.next
				curr.next = prev
				prev = curr
				curr = nxt
			return prev
		temp = head
		alternate = head.next
		start = alternate
		while temp and alternate and temp.next and alternate.next:
			temp.next = temp.next.next
			temp = temp.next
			alternate.next = temp.next
			alternate = alternate.next
		start = reverse(start)
		temp.next = start
		return temp


class Solution:

	def rearrange(self, head):
		link = head
		final = Node(-1)
		x = final
		while link != None and link.next != None:
			final.next = link.next
			if final.next != None:
				final = final.next
			link.next = link.next.next
			if link.next == None or link.next.next == None:
				y = self.reverse(x.next)
				link.next = y
				break
			link = link.next
		return head

	def reverse(self, head):
		prev = None
		current = head
		while current is not None:
			nex = current.next
			current.next = prev
			prev = current
			current = nex
		head = prev
		return head


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None or head.next.next == None:
			return head
		even = head
		odd = head.next
		cur = head.next.next
		even.next = odd.next = None
		check = 1
		while cur:
			if check == 1:
				even.next = cur
				cur = cur.next
				even = even.next
				check = 0
			else:
				temp = cur.next
				cur.next = odd
				odd = cur
				cur = temp
				check = 1
		even.next = odd
		return head


class Solution:

	def rearrange(self, head):
		head2 = Node(0)
		(p, q) = (head2, None)
		while True:
			if head:
				p.next = head
				p = p.next
				head = head.next
			else:
				break
			if head:
				temp = head
				head = head.next
				temp.next = q
				q = temp
			else:
				break
		p.next = q
		return head2.next

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in reversed(values):
			llist.push(i)
		Solution().rearrange(llist.head)
		llist.printList()
		t -= 1


class Solution:

	def rearrange(self, head):
		if head == None or head.next == None or head.next.next == None:
			return head
		even = head
		odd = head.next
		cur = head.next.next
		even.next = odd.next = None
		check = 1
		while cur != None:
			if check == 1:
				even.next = cur
				cur = cur.next
				even = even.next
				check = 0
			else:
				temp = cur.next
				cur.next = odd
				odd = cur
				cur = temp
				check = 1
		even.next = odd
		return head

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in reversed(values):
			llist.push(i)
		Solution().rearrange(llist.head)
		llist.printList()
		t -= 1


class Solution:

	def rearrange(self, head):
		flag = True
		curr = head
		even_stk = []
		odd_stk = []
		while curr != None:
			if flag:
				even_stk.append(curr)
				flag = False
			else:
				odd_stk.append(curr)
				flag = True
			curr = curr.next
		head = even_stk[0]
		curr = head
		for i in range(1, len(even_stk)):
			curr.next = even_stk[i]
			curr = curr.next
		for i in range(len(odd_stk)):
			curr.next = odd_stk.pop()
			curr = curr.next
		curr.next = None
		return head

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in reversed(values):
			llist.push(i)
		Solution().rearrange(llist.head)
		llist.printList()
		t -= 1


class Solution:

	def rearrange(self, head):
		li = []
		li1 = []
		temp = head
		while temp:
			li.append(temp.data)
			temp = temp.next
			if temp:
				li1.append(temp.data)
				temp = temp.next
		temp = head
		li1.reverse()
		for i in range(0, len(li)):
			temp.data = li[i]
			temp = temp.next
		for i in li1:
			temp.data = i
			temp = temp.next
		return head

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in reversed(values):
			llist.push(i)
		Solution().rearrange(llist.head)
		llist.printList()
		t -= 1


class Solution:

	def rearrange(self, head):
		o = []
		e = []
		temp = head
		c = 0
		while temp is not None:
			if c % 2 == 0:
				o.append(temp.data)
			else:
				e.append(temp.data)
			c += 1
			temp = temp.next
		o.extend(e[::-1])
		temp = head
		for i in o:
			temp.data = i
			temp = temp.next

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in reversed(values):
			llist.push(i)
		Solution().rearrange(llist.head)
		llist.printList()
		t -= 1


class Solution:

	def rearrange(self, head):
		head1 = None
		temp = head
		while temp and temp.next:
			node = Node(temp.next.data)
			node.next = head1
			head1 = node
			temp.next = temp.next.next
			temp = temp.next
		tail = head
		while tail.next:
			tail = tail.next
		tail.next = head1
		return head

class Node:

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

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while temp:
			print(temp.data, end=' ')
			temp = temp.next
		print()
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		llist = LinkedList()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in reversed(values):
			llist.push(i)
		Solution().rearrange(llist.head)
		llist.printList()
		t -= 1


class Solution:

	def rearrange(self, head):
		if head.next is None:
			return head
		if head.next.next is None:
			return head
		current = head
		n = head.next
		head2 = n
		temp = None
		while current and n and n.next:
			current.next = n.next
			n.next = n.next.next
			current = current.next
			n = n.next
		if current.next is None or (current.next == n and n.next is None):
			temp = current
		current2 = head2
		prev = None
		n = None
		while current2:
			n = current2.next
			current2.next = prev
			prev = current2
			current2 = n
		temp.next = prev
		return head


class Solution:

	def rearrange(self, head):
		if head is None or head.next is None:
			return
		odd = head
		ehead = even = head.next
		while odd.next.next and even.next.next:
			odd.next = odd.next.next
			odd = odd.next
			even.next = even.next.next
			even = even.next
		if odd.next.next:
			odd.next = odd.next.next
			odd = odd.next
			even.next = None
		pre = None
		cur = ehead
		while cur:
			nex = cur.next
			cur.next = pre
			pre = cur
			cur = nex
		odd.next = pre


class Solution:

	def rearrange(self, head):
		(c, prev2) = (head, None)
		alt = Node(0)
		nh = alt
		while c and c.next:
			alt.next = Node(c.next.data)
			alt = alt.next
			if c.next.next is None:
				break
			c.next = c.next.next
			c = c.next
		(cr, pre) = (nh.next, None)
		while cr:
			temp = cr.next
			cr.next = pre
			pre = cr
			cr = temp
		c.next = pre
		return nh.next


class Solution:

	def rearrange(self, head):
		two = []
		odd = head
		even = head.next
		while odd.next != None and even.next != None:
			two.append(even)
			odd.next = odd.next.next
			even = even.next.next
			odd = odd.next
		if even != None:
			two.append(even)
		for i in range(len(two)):
			odd.next = two.pop()
			odd = odd.next
		odd.next = None
		return


class Solution:

	def rearrange(self, head):
		x = head
		y = []
		z = []
		i = 0
		while x:
			if i % 2 != 0:
				y.append(x.data)
			else:
				z.append(x.data)
			i += 1
			x = x.next
		y = y[::-1]
		z.extend(y)
		temp = head
		head = temp
		i = 0
		while temp != None:
			temp.data = z[i]
			i += 1
			temp = temp.next


class Solution:

	def rearrange(self, head):
		if head.next is None:
			return head
		t1 = head
		x = t1.next.next
		firstTime = True
		while t1.next is not None and x is not None:
			t2 = t1.next
			if firstTime:
				t2.next = None
				firstTime = False
			t1.next = x
			t1 = t1.next
			if x.next is None:
				t1.next = t2
				return head
			x = t1.next.next
			t1.next.next = t2
		return head