Given a singly linked list L_{0} -> L_{1} -> … -> L_{n-1} -> L_{n}. Rearrange the nodes in the list so that the new formed list is: L_{0} -> L_{n} -> L_{1} -> L_{n-1} -> L_{2} -> L_{n-2}.
Input:
You have to complete the method which takes 1 argument: the head of the  linked list. You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually.
Output:
Your function should return a pointer to the rearranged list so obtained.
User Task:
The task is to complete the function inPlace() which should rearrange the given linked list as required.
Constraints:
1 <=T<= 50
1 <= size of linked lists <= 100
Example:
Input:
2
4
1 2 3 4
5
1 2 3 4 5 
Output:
1 4 2 3
1 5 2 4 3
Explanation:
Testcase 1: After rearranging the linked list as required, we have 1, 4, 2 and 3 as the elements of the linked list.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

def inPlace(root):
    #code here

Solutions:
def inPlace(root):
	t = root
	k = []
	while t != None:
		k.append(t.data)
		t = t.next
	i = 0
	j = len(k) - 1
	l = 0
	t = root
	while l < len(k):
		if l % 2 == 0:
			t.data = k[i]
			i += 1
			l = l + 1
			t = t.next
		else:
			t.data = k[j]
			j = j - 1
			l = l + 1
			t = t.next
	return root


def mergeList(head1, head2):
	temp1 = head1
	temp2 = head2
	while temp1 and temp2:
		nxt1 = temp1.next
		nxt2 = temp2.next
		temp1.next = temp2
		temp2.next = nxt1
		temp1 = nxt1
		temp2 = nxt2
	return [head1, temp2]

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

def inPlace(head):
	slow = fast = head
	while fast and fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	nxt = slow.next
	slow.next = None
	head2 = reverse(nxt)
	(h1, h2) = mergeList(head, head2)
	return h1


def inPlace(root):
	stack = [root]
	while stack[-1].next:
		current = stack[-1]
		stack.append(stack[-1].next)
	if len(stack) == 1:
		return root
	else:
		firstNode = stack.pop(0)
		secondNode = stack.pop()
		firstNode.next = secondNode
		lastNode = secondNode
		while len(stack) > 1:
			firstNode = stack.pop(0)
			secondNode = stack.pop()
			lastNode.next = firstNode
			firstNode.next = secondNode
			lastNode = secondNode
		if len(stack) == 0:
			lastNode.next = None
		else:
			finalNode = stack.pop()
			lastNode.next = finalNode
			finalNode.next = None
		return root


def inPlace(root):
	t = root
	c = 0
	n = 0
	l1 = []
	l2 = []
	while t:
		n += 1
		t = t.next
	m = root
	while m:
		if c < n // 2:
			l1.append(m.data)
			c += 1
		else:
			l2.append(m.data)
			c += 1
		m = m.next
	l2.reverse()
	l = []
	j = 0
	k = 0
	for i in range(n // 2):
		l.append(l1[j])
		j += 1
		l.append(l2[k])
		k += 1
	if len(l1) != len(l2):
		l.append(l2[k])
	l.reverse()
	h1 = Node(l[0])
	l.remove(l[0])
	for item in l:
		node = Node(item)
		node.next = h1
		h1 = node
	return h1


def inPlace(root):
	if root is None:
		return None
	(slow, fast) = (root, root.next)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	mid = slow.next
	(slow.next, prev) = (None, None)
	while mid:
		next = mid.next
		mid.next = prev
		prev = mid
		mid = next
	cur = root
	while cur and prev:
		n1 = cur.next
		n2 = prev.next
		cur.next = prev
		prev.next = n1
		cur = n1
		prev = n2
	return root


def inPlace(root):
	p = root
	l1 = []
	l2 = []
	while p:
		l1.append(p.data)
		p = p.next
	j = len(l1) - 1
	for i in range(len(l1) // 2):
		l2.append(l1[i])
		l2.append(l1[j])
		j -= 1
	if len(l1) % 2 != 0:
		l2.append(l1[len(l1) // 2])
	dummy = Node(0)
	n0 = dummy
	for i in l2:
		n0.next = Node(i)
		n0 = n0.next
	return dummy.next


def inPlace(root):
	l = []
	temp = root
	while temp:
		l.append(temp.data)
		temp = temp.next
	j = 0
	k = -1
	ind = 1
	temp = root
	while temp:
		if ind % 2:
			temp.data = l[j]
			j += 1
		else:
			temp.data = l[k]
			k -= 1
		ind += 1
		temp = temp.next
	return root


def inPlace(root):
	head = root
	l = []
	while head.next:
		head = head.next
		l.append(head)
	head = root
	while True:
		head.next = l.pop()
		head = head.next
		if not l:
			head.next = None
			return root
		head.next = l.pop(0)
		head = head.next
		if not l:
			head.next = None
			return root


def inPlace(root):
	if root is None or root.next is None:
		return root
	(slow, fast) = (root, root)
	while fast is not None and fast.next is not None:
		slow = slow.next
		fast = fast.next.next
	second = slow.next
	slow.next = None
	prev = None
	while second:
		nxt = second.next
		second.next = prev
		prev = second
		second = nxt
	(first, second) = (root, prev)
	while second:
		(temp1, temp2) = (first.next, second.next)
		first.next = second
		second.next = temp1
		(first, second) = (temp1, temp2)
	return root


def inPlace(root):
	b = []
	tmp = root
	tmp1 = root
	while tmp != None:
		b.append(tmp.data)
		tmp = tmp.next
	c = []
	j = len(b) - 1
	while j >= 0:
		c.append(b[j])
		j -= 1
	a = []
	i = 0
	j = 0
	while i < len(b):
		a.append(b[j])
		if i < len(b) - 1:
			a.append(c[j])
		i += 2
		j += 1
	for i in range(len(b)):
		tmp1.data = a[i]
		tmp1 = tmp1.next
	return root


def inPlace(head):
	slow = head
	fast = head
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
	head1 = head
	head2 = slow.next
	slow.next = None

	def reverse(head):
		prev = None
		curr = head
		next1 = None
		while curr != None:
			next1 = curr.next
			curr.next = prev
			prev = curr
			curr = next1
		return prev
	p = None
	headp = None
	count = 0
	head2 = reverse(head2)
	n = head1
	m = head2
	while n != None and m != None:
		if count % 2 == 0:
			if p == None:
				p = n
				headp = n
			else:
				p.next = n
				p = p.next
			n = n.next
		else:
			if p == None:
				p = m
				headp = p
			else:
				p.next = m
				p = p.next
			m = m.next
		count += 1
	if n != None:
		p.next = n
		p = p.next
	elif m != None:
		p.next = m
		p = p.next
	return headp


def inPlace(root):
	l = []
	cur = root
	while cur:
		l.append(cur.data)
		cur = cur.next
	dummy = Node(0)
	cur = dummy
	(left, right) = (0, len(l) - 1)
	while left < right:
		cur.next = Node(l[left])
		cur = cur.next
		left += 1
		cur.next = Node(l[right])
		cur = cur.next
		right -= 1
		if left == right:
			cur.next = Node(l[left])
			cur = cur.next
	return dummy.next


def reverse(head):
	temp = head
	t1 = None
	while temp.next != None:
		t2 = temp
		temp = temp.next
		t2.next = t1
		t1 = t2
	temp.next = t1
	head = temp
	return head

def count(head):
	c = 0
	temp = head
	while temp:
		temp = temp.next
		c += 1
	return c

def inPlace(root):
	if root:
		r = count(root)
		head1 = None
		tail1 = None
		c = 0
		temp = root
		while c != r // 2:
			if head1 == None:
				head1 = temp
				tail1 = temp
			else:
				tail1.next = temp
				tail1 = tail1.next
			c += 1
			temp = temp.next
		tail1.next = None
		head2 = None
		tail2 = None
		while temp:
			if head2 == None:
				head2 = temp
				tail2 = temp
			else:
				tail2.next = temp
				tail2 = tail2.next
			temp = temp.next
		tail2.next = None
		a = reverse(head2)
		t1 = head1
		t2 = a
		prev = None
		while t1 and t2:
			b = t1.next
			t1.next = t2
			c = t2.next
			t2.next = b
			prev = t1.next
			t1 = t1.next.next
			t2 = c
		if t2 is not None:
			prev.next = t2
		return head1


def inPlace(head):
	import math
	count = 0
	tmp = head
	while tmp:
		tmp = tmp.next
		count += 1
	count = math.ceil(count / 2) - 1
	curr = head
	while count > 0:
		nxt = curr.next
		beforeLast = head
		while beforeLast.next.next:
			beforeLast = beforeLast.next
		last = beforeLast.next
		curr.next = last
		last.next = nxt
		beforeLast.next = None
		curr = nxt
		count -= 1
	return head


def inPlace(head):
	slow = head
	fast = head
	p = head
	while fast != None and fast.next != None:
		p = slow
		slow = slow.next
		fast = fast.next.next
	if fast == None:
		p.next = None
	else:
		d = slow
		slow = slow.next
		d.next = None
	d = None
	while slow != None:
		n = slow.next
		slow.next = d
		d = slow
		slow = n
	t = head
	temp1 = head
	temp2 = d
	while d != None:
		temp1 = t
		t = t.next
		temp1.next = d
		temp2 = d
		d = d.next
		temp2.next = t
	if t != None and temp2 != None:
		temp2.next = t
	return head


def inPlace(root):
	itr = root
	new = []
	h = []
	while itr:
		h.append(itr.data)
		itr = itr.next
	l = len(h)
	j = l - 1
	for i in range(l // 2):
		new.append(h[i])
		new.append(h[j])
		j -= 1
	if l % 2 != 0:
		new.append(h[l // 2])
	temp = root
	i = 0
	while temp:
		temp.data = new[i]
		temp = temp.next
		i += 1
	return root


def inPlace(root):
	h = root
	li = []
	while h:
		li.append(h.data)
		h = h.next
	h = root
	while h:
		h.data = li.pop(0)
		h = h.next
		if h != None:
			h.data = li.pop()
			h = h.next
	return root


def inPlace(root):
	temp = root
	l = []
	n = 0
	while temp:
		l.append(temp.data)
		n += 1
		temp = temp.next
	ll = Llist()
	tail = ll.head
	if n % 2 == 0:
		for i in range(n // 2):
			tail = ll.insert(l[i], tail)
			tail = ll.insert(l[-1 - i], tail)
	elif n % 2 != 0:
		for i in range(n // 2):
			tail = ll.insert(l[i], tail)
			tail = ll.insert(l[-1 - i], tail)
		tail = ll.insert(l[n // 2], tail)
	return ll.head


def inPlace(root):

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

	def reverse(head):
		if head == None:
			return
		currNode = head
		prev = None
		while currNode != None:
			nxt = currNode.next
			currNode.next = prev
			prev = currNode
			currNode = nxt
		return prev
	if root == None:
		return
	mid = middleNode(root)
	midNode = mid.next
	mid.next = None
	head1 = reverse(midNode)
	currNode = root
	while currNode != None and head1 != None:
		nxt = currNode.next
		tmp = head1.next
		currNode.next = head1
		head1.next = nxt
		currNode = nxt
		head1 = tmp
	return root


def inPlace(root):
	l = []
	p = root
	while p:
		l.append(p.data)
		p = p.next
	if len(l) % 2 == 0:
		p = len(l) // 2
	else:
		p = len(l) // 2 + 1
	ll = l[:p]
	lll = l[p:][::-1]
	t = []
	for i in range(p - 1):
		t.append(ll[i])
		t.append(lll[i])
	if len(l) % 2 != 0:
		t.append(ll[-1])
	else:
		t.append(ll[-1])
		t.append(lll[-1])
	tt = root
	for i in t:
		tt.data = i
		tt = tt.next
	return root


def inPlace(head):
	(slow, fast) = (head, head.next)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	second = slow.next
	prev = slow.next = None
	while second:
		tmp = second.next
		second.next = prev
		prev = second
		second = tmp
	(first, second) = (head, prev)
	while second:
		(tmp1, tmp2) = (first.next, second.next)
		first.next = second
		second.next = tmp1
		(first, second) = (tmp1, tmp2)
	return head


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

def inPlace(A):
	slow = A
	fast = A
	while fast.next and fast.next.next:
		fast = fast.next.next
		slow = slow.next
	head1 = A
	head2 = slow.next
	slow.next = None
	head2 = reverse(head2)
	node = Node(0)
	ans = node
	i = 1
	while head1 and head2:
		if i % 2 == 0:
			node.next = Node(head2.data)
			head2 = head2.next
			node = node.next
		else:
			node.next = Node(head1.data)
			head1 = head1.next
			node = node.next
		i += 1
	while head1:
		node.next = Node(head1.data)
		head1 = head1.next
		node = node.next
	while head2:
		node.next = Node(head2.data)
		head2 = head2.next
		node = node.next
	return ans.next


def getMiddle(ptr):
	slow = ptr
	fast = ptr
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	return slow

def reverse(ptr):
	prev = None
	curr = ptr
	while curr:
		(next, curr.next) = (curr.next, prev)
		(prev, curr) = (curr, next)
	return prev

def inPlace(root):
	middle = getMiddle(root)
	head2 = middle.next
	middle.next = None
	head2 = reverse(head2)
	dummy = Node(-1)
	temp = dummy
	while root:
		temp.next = root
		temp = temp.next
		root = root.next
		if head2 != None:
			temp.next = head2
			head2 = head2.next
			temp = temp.next
	return dummy.next


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

def inPlace(head):
	First = head
	slow = head
	fast = head.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	Shead = slow.next
	slow.next = None
	Second = reverse(Shead)
	while Second:
		tem1 = First.next
		tem2 = Second.next
		First.next = Second
		Second.next = tem1
		First = tem1
		Second = tem2
	return head


def inPlace(root):
	(slow, fast) = (root, root.next)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	second = slow.next
	prev = slow.next = None
	while second:
		temp = second.next
		second.next = prev
		prev = second
		second = temp
	(first, second) = (root, prev)
	while second:
		(temp1, temp2) = (first.next, second.next)
		first.next = second
		second.next = temp1
		(first, second) = (temp1, temp2)
	return root


def inserti(root, data):
	new_node = Node(data)
	if root is None:
		root = new_node
		return root
	cur = root
	while cur.next:
		cur = cur.next
	cur.next = new_node
	return root

def arrp(root):
	if root is None:
		return []
	res = []
	cur = root
	while cur:
		res.append(cur.data)
		cur = cur.next
	return res

def inPlace(root):
	res = arrp(root)
	if len(res) % 2 == 0:
		mid = len(res) // 2
	else:
		mid = len(res) // 2 + 1
	left = res[:mid]
	right = res[mid:]
	kl = None
	j = len(right) - 1
	for i in range(len(left)):
		kl = inserti(kl, left[i])
		if j >= 0:
			kl = inserti(kl, right[j])
			j -= 1
	return kl


def reverse(root):
	prev = None
	temp = root
	next = None
	while temp:
		next = temp.next
		temp.next = prev
		prev = temp
		temp = next
	return prev

def inPlace(A):
	slow = A
	fast = A
	while fast.next and fast.next.next:
		fast = fast.next.next
		slow = slow.next
	head1 = A
	head2 = slow.next
	slow.next = None
	head2 = reverse(head2)
	node = Node(0)
	ans = node
	i = 1
	while head1 and head2:
		if i % 2 == 0:
			node.next = Node(head2.data)
			head2 = head2.next
			node = node.next
		else:
			node.next = Node(head1.data)
			head1 = head1.next
			node = node.next
		i += 1
	while head1:
		node.next = Node(head1.data)
		head1 = head1.next
		node = node.next
	while head2:
		node.next = Node(head2.data)
		head2 = head2.next
		node = node.next
	return ans.next


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

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

def inPlace(root):
	mid = getMiddle(root)
	head2 = mid.next
	mid.next = None
	head2 = reverse(head2)
	dummy = Node(-1)
	temp = dummy
	while root != None:
		temp.next = root
		temp = temp.next
		root = root.next
		if head2 != None:
			temp.next = head2
			head2 = head2.next
			temp = temp.next
	return dummy.next


def inPlace(root):
	arr = []
	while root != None:
		arr.append(root)
		root = root.next
	n = len(arr)
	for i in range(n // 2):
		arr[i].next = arr[n - 1]
		arr[n - 1].next = arr[i + 1]
		n -= 1
		arr[i + 1].next = None
	return arr[0]


def inPlace(root):
	(slow, fast) = (root, root)
	while fast.next and fast.next.next:
		fast = fast.next.next
		slow = slow.next
	prev = None
	cur = slow.next
	while cur:
		nxt = cur.next
		cur.next = prev
		prev = cur
		cur = nxt
	slow.next = None
	head1 = root
	head2 = prev
	while head2:
		nxt1 = head1.next
		nxt2 = head2.next
		head1.next = head2
		head1 = nxt1
		head2.next = head1
		head2 = nxt2
	return root


def inPlace(root):
	p = root
	l = []
	while p is not None:
		l.append(p.data)
		p = p.next
	res = []
	if len(l) % 2 == 1:
		q = l[:len(l) // 2]
		r = l[len(l) // 2 + 1:]
		r.reverse()
		for i in range(len(q)):
			res.append(q[i])
			res.append(r[i])
		res.append(l[len(l) // 2])
	else:
		q = l[:len(l) // 2]
		r = l[len(l) // 2:]
		r.reverse()
		for i in range(len(q)):
			res.append(q[i])
			res.append(r[i])
	t = Llist()
	tail = root
	for i in res:
		tail = t.insert(i, tail)
	return t.head


def inPlace(root):
	(t, s) = (root, [])
	while t:
		s.append(t.data)
		t = t.next
	(i, j) = (0, len(s) - 1)
	t = root
	f = 0
	while i <= j:
		if f % 2 == 0:
			t.data = s[i]
			i += 1
			f = 1
		else:
			t.data = s[j]
			j -= 1
			f = 0
		t = t.next
	return root


def inPlace(head):
	arr = []
	while head:
		arr.append(head.data)
		head = head.next
	n = len(arr)
	res = []
	res.append(arr[0])
	st = 1
	en = n - 1
	while st <= en:
		if st == en:
			res.append(arr[st])
		res.append(arr[en])
		res.append(arr[st])
		st = st + 1
		en = en - 1
	dummy = Node(-1)
	move = dummy
	for i in range(n):
		new_node = Node(res[i])
		move.next = new_node
		move = new_node
	return dummy.next


def inPlace(r):
	l = []
	while r:
		l.append(r)
		r = r.next
	i = 0
	n = len(l)
	j = n - 1
	b = []
	while i <= j:
		b.append(l[i])
		i += 1
		if i > j:
			break
		b.append(l[j])
		j -= 1
	for i in range(n - 1):
		b[i].next = b[i + 1]
	b[-1].next = None
	return b[0]


def countNodes(head):
	count = 0
	current = head
	while current != None:
		count += 1
		current = current.next
	return count

def get_half_head(head, n_steps):
	if n_steps == 0:
		return head
	current = head
	while n_steps > 0:
		current = current.next
		n_steps -= 1
	return current

def reverseList(head):
	if head == None:
		return None
	if head.next == None:
		return head
	prev = None
	current = head
	next_node = head.next
	while next_node != None:
		current.next = prev
		prev = current
		current = next_node
		next_node = next_node.next
	current.next = prev
	return current

def inPlace(root):
	head = root
	nodes_count = countNodes(head)
	if nodes_count <= 2:
		return head
	n_steps = nodes_count // 2
	half_head = get_half_head(head, n_steps)
	reversed_head = reverseList(half_head)
	count = 1
	current1 = head
	current2 = reversed_head
	while count <= nodes_count:
		if count % 2 != 0:
			tmp = current2.next
			current2.next = current1.next
			current1.next = current2
			current2 = tmp
		current1 = current1.next
		count += 1
	current1.next = None
	return head


def inPlace(head):
	slow = head
	fast = head
	a = []
	b = []
	while fast and fast.next:
		a.append(slow.data)
		slow = slow.next
		fast = fast.next.next
	if fast != None:
		a.append(slow.data)
		slow = slow.next
	while slow:
		b.append(slow.data)
		slow = slow.next
	temp = head
	head = temp
	b = b[::-1]
	i = 0
	j = 0
	c = 0
	while temp:
		if c % 2 == 0:
			temp.data = a[i]
			i += 1
		else:
			temp.data = b[j]
			j += 1
		c += 1
		temp = temp.next
	return head


def inPlace(root):
	if root == None:
		return root
	if root.next == None:
		return root
	temp = root
	while temp.next.next != None:
		temp = temp.next
	temp1 = temp.next
	temp.next = None
	a = inPlace(root.next)
	root.next = temp1
	temp1.next = a
	return root


def inPlace(root):
	nodes = []
	temp = root
	while temp != None:
		nodes.append(temp)
		temp = temp.next
	head = nodes[0]
	temp = head
	nodes.pop(0)
	turn = 0
	while nodes != []:
		if turn % 2 == 0:
			temp.next = nodes.pop()
			temp = temp.next
		else:
			temp.next = nodes.pop(0)
			temp = temp.next
		turn += 1
	temp.next = None
	return head


def reverse(value):
	thisvalue = value
	previous = None
	while thisvalue:
		nxt = thisvalue.next
		thisvalue.next = previous
		previous = thisvalue
		thisvalue = nxt
	return previous

def inPlace(root):
	cur = root
	count = 0
	while cur:
		cur = cur.next
		count += 1
	mid = count // 2
	temp = root
	count = 0
	while temp:
		if count == mid:
			nxt = temp.next
			temp.next = None
		count += 1
		temp = temp.next
	cur = root
	thisvalue = reverse(nxt)
	prev = thisvalue
	nxt2 = thisvalue.next
	while cur and thisvalue:
		if cur == root:
			nxt1 = cur.next
			cur.next = thisvalue
		else:
			nxt1 = cur.next
			nxt2 = thisvalue.next
			prev.next = cur
			cur.next = thisvalue
		prev = thisvalue
		cur = nxt1
		thisvalue = nxt2
	prev.next = cur
	return root


def inPlace(root):
	nodes = []
	temp = root
	while temp != None:
		nodes.append(temp)
		temp = temp.next
	head = nodes[0]
	temp = head
	nodes.pop(0)
	turn = 0
	while nodes != []:
		if turn % 2 == 0:
			temp.next = nodes.pop()
			temp = temp.next
		else:
			temp.next = nodes.pop(0)
			temp = temp.next
		turn += 1
	temp.next = None
	return head

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 printList(head):
	tmp = head
	while tmp != None:
		print(tmp.data, end=' ')
		tmp = tmp.next
	print()
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)
		res = inPlace(ll.head)
		printList(res)


def inPlace(head):

	def reverse(temp):
		prev = None
		next_var = None
		while temp:
			next_var = temp.next
			temp.next = prev
			prev = temp
			temp = next_var
		return prev
	l = 1
	temp = head
	while temp.next:
		temp = temp.next
		l += 1
	if l == 1:
		return
	mid = head.next
	i = 0
	while i < l // 2:
		prev1 = mid
		mid = mid.next
		i += 1
	prev1.next = None
	head2 = reverse(mid)
	head1 = head
	while head2:
		next_v1 = head1.next
		head1.next = head2
		next_v2 = head2.next
		head2.next = next_v1
		head2 = next_v2
		head1 = head1.next.next
	return head


def inPlace(root):

	def reverse(root):
		(prev, curr, next) = (None, root, None)
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		return prev
	(s, f) = (root, root)
	while f and f.next:
		s = s.next
		f = f.next.next
	rev = reverse(s.next)
	s.next = None
	h = root
	while rev and h:
		t = h.next
		h.next = rev
		tt = rev.next
		rev.next = t
		h = t
		rev = tt
	return root


def reverse(root):
	prev = None
	curr = root
	while root != None:
		curr = root
		root = root.next
		curr.next = prev
		prev = curr
	return prev

def inPlace(root):
	fast = root
	slow = root
	while fast != None and fast.next != None:
		fast = fast.next.next
		slow = slow.next
	head1 = root
	head2 = slow.next
	head2 = reverse(head2)
	slow.next = None
	head = Node(0)
	curr = head
	while head1 or head2:
		if head1:
			curr.next = head1
			curr = curr.next
			head1 = head1.next
		if head2:
			curr.next = head2
			curr = curr.next
			head2 = head2.next
	return head.next


def inPlace(root):
	slow = root
	fast = root
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	head = slow
	prev = None
	next = None
	cur = head
	while cur:
		next = cur.next
		cur.next = prev
		prev = cur
		cur = next
	head = prev
	p_curr = root
	q_curr = head
	while p_curr.next != None and q_curr.next != None:
		p_next = p_curr.next
		q_next = q_curr.next
		q_curr.next = p_next
		p_curr.next = q_curr
		p_curr = p_next
		q_curr = q_next
	return root


def inPlace(root):
	if not root or not root.next or (not root.next.next):
		return root
	first = root
	while first and first.next:
		temp = first
		while temp.next.next:
			temp = temp.next
		last = temp.next
		temp.next = None
		last.next = first.next
		first.next = last
		first = first.next.next
	return root


def inPlace(root):
	arr = []
	arr1 = []
	temp = root
	while temp != None:
		arr.append(temp.data)
		temp = temp.next
	ln = len(arr)
	for i in range(0, ln // 2):
		arr1.append(arr[i])
		arr1.append(arr[ln - 1 - i])
	if ln % 2 != 0:
		arr1.append(arr[ln // 2])
	ll1 = Llist()
	tail = None
	for nodeData in arr1:
		tail = ll1.insert(nodeData, tail)
	return ll1.head


def reverse(root):
	curr = root
	prev = None
	while curr:
		next1 = curr.next
		curr.next = prev
		prev = curr
		curr = next1
	return prev

def inPlace(root):
	fast = root
	slow = root
	prev_slow = None
	while fast and fast.next:
		fast = fast.next.next
		prev_slow = slow
		slow = slow.next
	if fast:
		prev_slow = slow
		slow = slow.next
	prev_slow.next = None
	new = reverse(slow)
	curr = root
	currn = new
	final = res = Node(None)
	while True:
		if not currn and (not curr):
			break
		final.next = curr
		final = final.next
		curr = curr.next
		if not curr:
			final.next = currn
			break
		final.next = currn
		final = final.next
		currn = currn.next
	return res.next


def inPlace(root):
	curr = root
	arr = []
	if root.next == None:
		return root
	elif root.next.next == None:
		return root
	while curr != None:
		arr.append(curr.data)
		curr = curr.next
	n = len(arr)
	if len(arr) % 2 == 0:
		curr = root
		for i in range(0, len(arr) // 2):
			curr.data = arr[i]
			curr = curr.next
			curr.data = arr[n - i - 1]
			curr = curr.next
		return root
	else:
		curr = root
		for i in range(0, (n - 1) // 2):
			curr.data = arr[i]
			curr = curr.next
			curr.data = arr[n - i - 1]
			curr = curr.next
		curr.data = arr[(n - 1) // 2]
		return root


from collections import deque

def inPlace(root):
	dq = deque()
	current = root
	current1 = root
	while current != None:
		dq.append(current.data)
		current = current.next
	position = 0
	while current1 != None:
		if position % 2 != 0:
			temp = dq.pop()
			current1.data = temp
			position += 1
		else:
			current1.data = dq.popleft()
			position += 1
		current1 = current1.next
	return root


def inPlace(root):
	l = []
	curr = root
	temp = root
	while curr:
		l.append(curr.data)
		curr = curr.next
	i = 0
	while root:
		root.data = l[i]
		root = root.next
		if root:
			root.data = l[-1 - i]
		if root is None:
			return temp
		i += 1
		root = root.next
	return temp


def inPlace(root):
	import math
	x = []
	while root:
		x.append(root.data)
		root = root.next
	n = len(x)
	t = math.ceil(n / 2)
	y = x[:t]
	z = x[t:]
	z = z[::-1]
	x.clear()
	if n % 2 == 0:
		for i in range(t):
			x.append(y[i])
			x.append(z[i])
	else:
		for i in range(t - 1):
			x.append(y[i])
			x.append(z[i])
		x.append(y[t - 1])
	p = Node(x[0])
	q = p
	for i in range(1, len(x)):
		new = Node(x[i])
		q.next = new
		q = new
	return p


def inPlace(root):
	mid = middle(root)
	secondhead = mid.next
	mid.next = None
	firsthead = root
	secondhead = reverse(secondhead)
	while firsthead and secondhead:
		secnext = secondhead.next
		firnext = firsthead.next
		firsthead.next = secondhead
		secondhead.next = firnext
		firsthead = firnext
		secondhead = secnext
	return root

def reverse(head):
	if head is None:
		return
	prev = None
	ptr = head
	while ptr:
		temp = ptr.next
		ptr.next = prev
		prev = ptr
		ptr = temp
	head = prev
	return head

def middle(head):
	if head is None:
		return
	if head.next is None:
		return head
	slow = fast = head
	while True:
		fast = fast.next.next
		if fast is None:
			return slow
		if fast.next is None:
			return slow.next
		slow = slow.next


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

def inPlace(root):
	slow = root
	fast = slow.next
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
	node1 = root
	node2 = slow.next
	slow.next = None
	node2 = reverseList(node2)
	node = Node(0)
	curr = node
	while node1 != None or node2 != None:
		if node1 != None:
			curr.next = node1
			curr = curr.next
			node1 = node1.next
		if node2 != None:
			curr.next = node2
			curr = curr.next
			node2 = node2.next
	node = node.next
	return node


def inPlace(root):
	s = root
	slow = s
	fast = s.next
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
	cur = slow.next
	slow.next = None
	p = None
	while cur.next:
		n = cur.next
		cur.next = p
		p = cur
		cur = n
	cur.next = p
	while cur:
		ne = s.next
		a = cur.next
		s.next = cur
		cur.next = ne
		s = ne
		cur = a
	return root


def inPlace(root):
	head = root

	class node:

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

	def rev(head):
		if head.next is None:
			return head
		if head.next.next is None:
			head.next.next = head
			h = head.next
			head.next = None
			return h
		p = head
		c = head.next
		n = head.next.next
		lst = []
		while True:
			if n is None:
				lst.append(c)
				c.next = p
				break
			else:
				c.next = p
				p = c
				c = n
				n = n.next
		head.next = None
		return lst[0]
	c = 0
	cur = head
	while True:
		if cur is None:
			break
		else:
			c += 1
			cur = cur.next
	if c % 2 == 0:
		c1 = 0
		ind = c // 2 + 1
		cur = head
		while True:
			if c1 == ind - 1:
				break
			else:
				c1 += 1
				cur = cur.next
		h = rev(cur)
		nul = node(0)
		l = head
		r = h
		n1 = node(1000000000.0)
		cur = nul
		for j in range(c // 2):
			cur.next = l
			cur = cur.next
			l = l.next
			cur.next = r
			r = r.next
			cur = cur.next
		cur.next = None
		return nul.next
	else:
		c1 = 0
		ind = c // 2 + 1
		cur = head
		while True:
			if c1 == ind - 1:
				break
			else:
				c1 += 1
				cur = cur.next
		h = rev(cur)
		nul = node(0)
		l = head
		r = h
		n1 = node(1000000000.0)
		cur = nul
		for j in range(c // 2):
			cur.next = l
			cur = cur.next
			l = l.next
			cur.next = r
			r = r.next
			cur = cur.next
		cur.next = l
		cur = cur.next
		cur.next = None
		return nul.next


def inPlace(root):
	prev = slow = fast = root
	while fast and fast.next:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	prev.next = None
	prev = None
	while slow:
		temp = slow.next
		slow.next = prev
		prev = slow
		slow = temp
	l1 = root
	l2 = prev
	while l1:
		l1Next = l1.next
		l2Next = l2.next
		l1.next = l2
		if not l1Next:
			break
		l2.next = l1Next
		l2 = l2Next
		l1 = l1Next
	return root


def printLink(head):
	s = ''
	while head:
		s = s + ' ' + str(head.data)
		head = head.next
	print(s)

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

def inPlace(root):
	if root == None or root.next == None or root.next.next == None:
		return root
	slow = root
	fast = root.next.next
	while fast and fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	if fast:
		h2 = slow.next.next
		slow.next.next = None
	else:
		h2 = slow.next
		slow.next = None
	h1 = root
	h2 = reverse(h2)
	h = None
	t1 = h1
	t2 = h2
	while t1 and t2:
		x = t1
		y = t2
		t1 = t1.next
		t2 = t2.next
		x.next = None
		y.next = None
		if h is None:
			h = x
			x.next = y
			y.next = None
			t = y
		else:
			t.next = x
			x.next = y
			y.next = None
			t = y
	if t2:
		t.next = t2
		t = t.next
		t.next = None
	if t1:
		t.next = t1
		t = t.next
		t.next = None
	return h


def reverse(head):
	prev = None
	cur = head
	while cur:
		temp = cur.next
		cur.next = prev
		prev = cur
		cur = temp
	return prev

def inPlace(head):
	prev_sp = None
	sp = head
	fp = head
	while fp and fp.next:
		prev_sp = sp
		sp = sp.next
		fp = fp.next.next
	prev_sp.next = None
	mid_node = None
	if fp:
		mid_node = sp
		second_half = mid_node.next
		mid_node.next = None
	else:
		second_half = sp
	second_half = reverse(second_half)
	i = 0
	first_half = head
	while first_half:
		if i % 2 == 0:
			first_half_temp = first_half.next
			first_half.next = second_half
			first_half = first_half_temp
		else:
			second_half_temp = second_half.next
			second_half.next = first_half
			second_half = second_half_temp
		i += 1
	if mid_node:
		second_half.next = mid_node
	return head


def inPlace(root):
	first = root
	second = root
	from copy import deepcopy
	mid = 0
	while second and second.next:
		mid += 1
		second = second.next.next
		prev1 = first
		first = first.next
	prev = None
	tmp = deepcopy(first)
	while tmp:
		tm = tmp.next
		tmp.next = prev
		prev = tmp
		if not tm:
			f_head = deepcopy(tmp)
		tmp = tm
	first = prev1
	first.next = None
	first = root
	while first:
		tmp = first.next
		rev_t = f_head.next
		f_head.next = tmp
		first.next = f_head
		first = first.next.next
		f_head = rev_t
	if f_head:
		tm = root
		while tm and tm.next:
			tm = tm.next
		tm.next = f_head
	return root


def inPlace(root):
	first = root
	second = root
	from copy import deepcopy
	mid = 0
	while second and second.next:
		mid += 1
		second = second.next.next
		prev1 = first
		first = first.next
	prev = None
	tmp = deepcopy(first)
	while tmp:
		tm = tmp.next
		tmp.next = prev
		prev = tmp
		if not tm:
			f_head = deepcopy(tmp)
		tmp = tm
	first = prev1
	first.next = None
	first = root
	new_head = None
	new_tail = None
	while first and f_head:
		if not new_head:
			node = first
			first = first.next
			new_head = new_tail = node
		else:
			node = first
			first = first.next
			new_tail.next = node
			new_tail = new_tail.next
		node = f_head
		new_tail.next = node
		new_tail = new_tail.next
		f_head = f_head.next
	return new_head


from collections import deque

def inPlace(root):
	dq = deque()
	currNode = root
	while currNode:
		dq.append(currNode.data)
		currNode = currNode.next
	currNode = root
	temp = 0
	while currNode:
		if temp % 2 == 0:
			currNode.data = dq.popleft()
		else:
			currNode.data = dq.pop()
		temp += 1
		currNode = currNode.next
	return root


def inPlace(head):
	slow = fast = head
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	prev = None
	curr = slow.next
	while curr:
		temp = curr.next
		curr.next = prev
		prev = curr
		curr = temp
	slow.next = None
	(head1, head2) = (head, prev)
	while head2:
		temp = head1.next
		head1.next = head2
		head1 = head2
		head2 = temp
	return head


def inPlace(root):
	a = []
	t = root
	while t != None:
		a.append(t.data)
		t = t.next
	final = []
	x = 1
	for i in range(len(a)):
		if x == 1:
			final.append(a[0])
			a.pop(0)
			x = 0
		else:
			final.append(a[len(a) - 1])
			a.pop()
			x = 1
	t = root
	i = 0
	while t is not None:
		t.data = final[i]
		i += 1
		t = t.next
	return root


def inPlace(root):
	s = []
	temp = root
	while temp:
		s.append(temp.data)
		temp = temp.next
	i = 0
	temp = root
	while len(s) > 0:
		if i % 2 == 0:
			temp.data = s[0]
			s.pop(0)
		else:
			temp.data = s[-1]
			s.pop()
		i += 1
		temp = temp.next
	return root


def inPlace(root):
	import math
	t = root
	arr = []
	while t is not None:
		arr.append(t.data)
		t = t.next
	left = []
	right = []
	l = len(arr)
	n = int(math.ceil(l / 2))
	for i in range(n):
		left.append(arr[i])
	for i in range(n, l):
		right.append(arr[i])
	right = right[::-1]
	res = [0] * l
	for i in range(0, l, 2):
		res[i] = left[int(i / 2)]
	for i in range(1, l, 2):
		res[i] = right[int(i // 2)]
	t = root
	i = 0
	while t is not None:
		t.data = res[i]
		i += 1
		t = t.next
	return root


def inPlace(root):
	head = root
	temp = root
	while temp.next != None:
		nextnode = temp.next
		prev = None
		while nextnode:
			newnode = nextnode.next
			nextnode.next = prev
			prev = nextnode
			nextnode = newnode
		temp.next = prev
		temp = prev
	return head


def inPlace(root):
	temp = root
	a = []
	while temp != None:
		a.append(temp.data)
		temp = temp.next
	b = []
	mid = len(a) // 2
	for (x, y) in zip(a[:mid], a[::-1]):
		b.append(x)
		b.append(y)
	if len(a) % 2 == 1:
		b.append(a[mid])
	temp = dummynode = Node(0)
	for x in b:
		newnode = Node(x)
		temp.next = newnode
		temp = newnode
	return dummynode.next


def inPlace(root):
	arr = []
	temp = root
	while temp:
		arr.append(temp.data)
		temp = temp.next
	arr1 = [0] * len(arr)
	j = len(arr) - 1
	i = 0
	k = 0
	while k < len(arr):
		if i == j:
			arr1[k] = arr[i]
		else:
			arr1[k] = arr[i]
			arr1[k + 1] = arr[j]
		j = j - 1
		i = i + 1
		k = k + 2
	temp = root
	i = 0
	while temp:
		temp.data = arr1[i]
		i = i + 1
		temp = temp.next
	return root


def inPlace(root):
	stack = []
	temp = []
	curr = root
	while curr:
		stack.append(curr.data)
		curr = curr.next
	for i in range(len(stack) // 2 + len(stack) % 2):
		temp.append(stack[i])
		if i != len(stack) - i - 1:
			temp.append(stack[len(stack) - i - 1])
	curr = root
	for i in range(len(temp)):
		curr.data = temp[i]
		curr = curr.next
	return root


def reverse(root):
	if root is None:
		return None
	if root.next is None:
		return root
	small_head = reverse(root.next)
	tail = root.next
	tail.next = root
	root.next = None
	return small_head

def length(root):
	c = 0
	while root is not None:
		c += 1
		root = root.next
	return c

def inPlace(root):
	curr_1 = root
	arr = []
	curr = root
	l = length(curr)
	curr = root
	while curr is not None:
		arr.append(curr.data)
		curr = curr.next
	new_arr = arr[::-1]
	final_arr = []
	for i in range(len(arr) // 2):
		final_arr.append(arr[i])
		final_arr.append(new_arr[i])
	if len(arr) % 2 != 0:
		final_arr.append(arr[i + 1])
	curr = root
	i = 0
	while curr is not None:
		curr.data = final_arr[i]
		i += 1
		curr = curr.next
	return root


def inPlace(root):
	lst = []
	while root:
		lst.append(root.data)
		root = root.next
	lkdlist = Llist()
	tail = None
	while lst:
		tail = lkdlist.insert(lst.pop(0), tail)
		if lst:
			tail = lkdlist.insert(lst.pop(), tail)
	return lkdlist.head


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

def inPlace(root):
	fast = root
	mid = root
	while fast and fast.next:
		fast = fast.next.next
		mid = mid.next
	hend = mid
	mid = mid.next
	hend.next = None
	sec = reverse(mid)
	head1 = root
	head2 = sec
	a = True
	while head1 and head2:
		if a:
			t1 = head1.next
			head1.next = head2
			head1 = t1
			a = False
		else:
			t2 = head2.next
			head2.next = head1
			head2 = t2
			a = True
	return root


def inPlace(root):
	arr = []
	res = []
	temp = root
	while temp:
		arr.append(temp.data)
		temp = temp.next
	length = len(arr)
	for i in range(len(arr) // 2):
		res.append(arr[i])
		res.append(arr[length - 1 - i])
	if length % 2 != 0:
		res.append(arr[length // 2])
	cur = root
	for val in res:
		cur.data = val
		cur = cur.next
	return root


def inPlace(root):
	temp = root
	l = []
	while temp:
		l.append(temp.data)
		temp = temp.next
	temp = root.next
	i = 1
	j = len(l) - 1
	while i < j:
		temp.data = l[j]
		temp = temp.next
		temp.data = l[i]
		temp = temp.next
		i += 1
		j -= 1
	if temp:
		temp.data = l[j]
	return root