Given a singly linked list: A0→A1→...→An-2→An-1, reorder it to: A0→An-1→A1→An-2→A2→An-3→...
For example: Given 1->2->3->4->5 its reorder is 1->5->2->4->3.
Note: It is recommended do this in-place without altering the node's values.
Example 1:
Input:
LinkedList: 1->2->3
Output: 1 3 2
Explanation:
Here n=3, so the correct
order is A0→A2→A1
Example 2:
Input:
Explanation: 1->7->3->4
Output: 1 4 7 3
Explanation:
Here n=4, so the correct
order is A0→A3→A1→A2
Your Task:
The task is to complete the function reorderList() which should reorder the list as required. The reorder list is automatically printed by the driver's code.
Note: Try to solve without using any auxilliary space.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 5*105
0 <= A[ i ] <= 105

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



#User function Template for python3



# Node Class    

class node:

    def __init__(self, val):

        self.data = val

        self.next = None



# Linked List Class

class Linked_List:

    def __init__(self):

        self.head = None

        self.tail = None





#Back-end complete function Template for Python 3

class Solution:

    

    def reorderList(self,head):

        pass

Solutions:
from collections import deque

class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		temp = deque([])
		curr = head
		while curr:
			temp.append(curr.data)
			curr = curr.next
		curr = head
		flag = True
		while temp:
			if flag:
				curr.data = temp.popleft()
				flag = False
			else:
				curr.data = temp.pop()
				flag = True
			curr = curr.next
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):

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

		def middle(head):
			slow = head
			fast = head
			while fast != None and fast.next != None:
				slow = slow.next
				fast = fast.next.next
			return slow
		mid = middle(head)
		hs = reverse(mid)
		hf = head
		while hf != None and hs != None:
			temp = hf.next
			hf.next = hs
			hf = temp
			temp = hs.next
			hs.next = hf
			hs = temp
			if hs == None:
				hf.next = None


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, 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:
			next = second.next
			second.next = prev
			prev = second
			second = next
		(first, second) = (head, prev)
		while second:
			(temp1, temp2) = (first.next, second.next)
			first.next = second
			second.next = temp1
			(first, second) = (temp1, temp2)
		pass
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):

		def reverselist(head):
			curr = head
			prev = None
			while curr != None:
				Next = curr.next
				curr.next = prev
				prev = curr
				curr = Next
			return prev

		def middlelist(head):
			slow = head
			fast = head
			while fast != None and fast.next != None:
				fast = fast.next.next
				slow = slow.next
			return slow
		middle = middlelist(head)
		middle_next = middle.next
		middle.next = None
		rev1 = reverselist(middle_next)
		curr = head
		while curr != None and rev1 != None:
			Next = curr.next
			rev1_next = rev1.next
			curr.next = rev1
			rev1.next = Next
			curr = Next
			rev1 = rev1_next
		return head


class node:

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

class Linked_List:

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

class Solution:

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

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

	def reorderList(self, head):
		if not head or not head.next:
			return head
		head2 = self.middle(head)
		head2 = self.reverse(head2)
		p = head
		q = head2
		while q:
			qnext = q.next
			q.next = p.next
			p.next = q
			p = q.next
			q = qnext
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if not head:
			return
		li = []
		tmp = head
		while tmp != None:
			li.append(tmp.data)
			tmp = tmp.next
		ans = []
		j = len(li) - 1
		k = 0
		for i in range(len(li)):
			if i & 1:
				ans.append(li[j])
				j -= 1
			else:
				ans.append(li[k])
				k += 1
		tmp = head
		tmp.data = ans[0]
		for i in range(1, len(ans)):
			ins = node(ans[i])
			tmp.next = ins
			tmp = ins
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):

		def reverse(head):
			p = head
			if p.next == None:
				return head
			else:
				th = p.next
			p.next = None
			while th.next:
				k = th.next
				th.next = p
				p = th
				th = k
			th.next = p
			return th
		n = 0
		th = head
		while th:
			n += 1
			th = th.next
		if n < 3:
			return head
		n -= 1
		n //= 2
		th = head
		hh = None
		for i in range(n):
			th = th.next
		hh = th.next
		th.next = None
		h2 = reverse(hh)
		h1 = head
		while h2:
			k1 = h1.next
			h1.next = h2
			k2 = h2.next
			h2.next = k1
			h1 = k1
			h2 = k2


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head == None or head.next == None:
			return
		(slow, fast) = (head, head)
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		second_half = slow.next
		slow.next = None
		(prev, curr, next_node) = (None, second_half, None)
		while curr:
			next_node = curr.next
			curr.next = prev
			prev = curr
			curr = next_node
		second_half = prev
		(first_half, second_half) = (head, second_half)
		while second_half:
			temp1 = first_half.next
			temp2 = second_half.next
			first_half.next = second_half
			second_half.next = temp1
			first_half = temp1
			second_half = temp2


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head is None or head.next is None:
			return head
		(prev, slow, fast) = (head, head, head)
		while fast and fast.next:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		mid = slow
		prev.next = None
		(prev1, curr) = (None, slow)
		while curr:
			nxt = curr.next
			curr.next = prev1
			prev1 = curr
			curr = nxt
		tmp = head
		st = node(-1)
		while tmp and prev1:
			st.next = tmp
			tmp = tmp.next
			st = st.next
			st.next = prev1
			prev1 = prev1.next
			st = st.next
		if tmp:
			st.next = tmp
		if prev1:
			st.next = prev1
		return st.next


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		(slow, fast) = (head, head.next)
		while fast is not None and fast.next is not None:
			slow = slow.next
			fast = fast.next.next
		new_head = slow.next
		slow.next = None
		new_head = self.reverse(new_head)
		(curr1, curr2) = (head, new_head)
		dummy_node = node(0)
		prev = dummy_node
		while curr1 is not None or curr2 is not None:
			if curr1 is not None:
				prev.next = curr1
				prev = prev.next
				curr1 = curr1.next
			if curr2 is not None:
				prev.next = curr2
				prev = prev.next
				curr2 = curr2.next
		return dummy_node.next

	def reverse(self, head):
		(prev_node, curr_node) = (None, head)
		while curr_node is not None:
			next_node = curr_node.next
			curr_node.next = prev_node
			prev_node = curr_node
			curr_node = next_node
		return prev_node


class node:

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

class Linked_List:

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

class Solution:

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

	def rev(self, head):
		dummy = None
		while head:
			next = head.next
			head.next = dummy
			dummy = head
			head = next
		return dummy

	def reorderList(self, head):
		mid = self.mid(head)
		c1 = head
		c2 = self.rev(mid.next)
		mid.next = None
		while c1 and c2:
			f1 = c1.next
			f2 = c2.next
			c1.next = c2
			c2.next = f1
			c1 = f1
			c2 = f2


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		l = []
		cur = head
		while cur:
			l.append(cur)
			cur = cur.next
		p = l[::-1]
		m = []
		for i in range(len(l)):
			m.append(l[i])
			m.append(p[i])
		m = m[:len(l)]
		m.append(None)
		cur = head = m[0]
		for i in range(1, len(m)):
			cur.next = m[i]
			cur = cur.next
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head.next is None:
			return
		a = []
		b = []
		temp = head
		while temp:
			a.append(temp)
			temp = temp.next
		n = len(a)
		if n % 2:
			k = (n + 1) // 2
		else:
			k = n // 2
		b = a[k:][::-1]
		temp = a[0]
		f = 1
		j = 0
		i = 1
		while j < len(b):
			if f:
				temp.next = b[j]
				j += 1
				f = 0
			else:
				temp.next = a[i]
				i += 1
				f = 1
			temp = temp.next
		if n % 2:
			temp.next = a[i]
			temp.next.next = None
		else:
			temp.next = None


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head == None or head.next == None:
			return
		n = 0
		walk = head
		while walk:
			walk = walk.next
			n = n + 1
		head2 = head
		for i in range((n - 1) // 2):
			head2 = head2.next
		tail = head2
		head2 = head2.next
		tail.next = None
		prv = None
		nex = head2.next
		while head2:
			nex = head2.next
			head2.next = prv
			prv = head2
			head2 = nex
		head2 = prv
		walk = head
		walk2 = head2
		while walk2:
			temp = walk.next
			walk.next = walk2
			walk = temp
			temp = walk2.next
			walk2.next = walk
			walk2 = temp
		if tail.next:
			tail = tail.next


class Solution:

	def reorderList(self, head):
		if head is None or head.next is None:
			return head
		slow = head
		fast = head
		while fast.next is not None and fast.next.next is not None:
			slow = slow.next
			fast = fast.next.next
		prev = None
		current = slow.next
		slow.next = None
		while current is not None:
			next_node = current.next
			current.next = prev
			prev = current
			current = next_node
		p1 = head
		p2 = prev
		while p2 is not None:
			next_node_p1 = p1.next
			next_node_p2 = p2.next
			p1.next = p2
			p2.next = next_node_p1
			p1 = next_node_p1
			p2 = next_node_p2
		return head


class Solution:

	def reorderList(self, head):
		slow = fast = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		l2 = slow.next
		slow.next = None
		prev = None
		while l2:
			nextt = l2.next
			l2.next = prev
			prev = l2
			l2 = nextt
		l1 = head
		l2 = prev
		while l1 and l2:
			nextt1 = l1.next
			nextt2 = l2.next
			l1.next = l2
			l2.next = nextt1
			l1 = nextt1
			l2 = nextt2


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if not head:
			return None
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		mid = slow
		curr = mid
		prev = None
		while curr:
			(curr.next, prev, curr) = (prev, curr, curr.next)
		rev_head = prev
		first = head
		second = rev_head
		while second.next:
			hop = first.next
			first.next = second
			first = hop
			hop = second.next
			second.next = first
			second = hop
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		arr = []
		temp = head
		count = 0
		while temp is not None:
			arr.append(temp.data)
			temp = temp.next
			count += 1
		temp = head
		pos = 0
		while temp is not None:
			temp.data = arr[pos]
			if not temp.next:
				break
			temp.next.data = arr[count - 1 - pos]
			pos += 1
			temp = temp.next.next
		return head


class node:

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

class Linked_List:

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

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

class Solution:

	def reorderList(self, head1):
		slow = fast = head1
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		nxt = slow.next
		slow.next = None
		head2 = reverse(nxt)
		tmp = head1
		while head1 and head2:
			nxt1 = head1.next
			nxt2 = head2.next
			head1.next = head2
			head2.next = nxt1
			head1 = nxt1
			head2 = nxt2
		return tmp


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head is None:
			return None
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		mid = slow
		prev = None
		cur = mid
		temp = cur.next
		while cur:
			temp = cur.next
			cur.next = prev
			prev = cur
			cur = temp
		second_head = prev
		(first, second) = (head, second_head)
		while second.next:
			next_hop = first.next
			first.next = second
			first = next_hop
			next_hop = second.next
			second.next = first
			second = next_hop
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, 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:
			nxt = second.next
			second.next = prev
			prev = second
			second = nxt
		(first, second) = (head, prev)
		while second:
			(tmp1, tmp2) = (first.next, second.next)
			first.next = second
			second.next = tmp1
			(first, second) = (tmp1, tmp2)
		pass
		return head


class node:

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

class Linked_List:

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

class Solution:

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

	def reorderList(self, head):
		(slow, fast) = (head, head)
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		first = head
		sec = slow.next
		slow.next = None
		sec = self.reverse(sec)
		while sec:
			(temp1, temp2) = (first.next, sec.next)
			first.next = sec
			sec.next = temp1
			(first, sec) = (temp1, temp2)


class node:

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

class Linked_List:

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

class Solution:

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

	def reorderList(self, head):
		(slow, fast) = (head, head)
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		first = head
		sec = slow.next
		slow.next = None
		dummy = node(0)
		res = dummy
		sec = self.reverse(sec)
		while first and sec:
			res.next = first
			res = res.next
			first = first.next
			res.next = sec
			res = res.next
			sec = sec.next
		if first:
			res.next = first
		if sec:
			res.next = sec
		return dummy


class node:

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

class Linked_List:

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

class Solution:

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

	def reorderList(self, head):
		slow = head
		fast = head.next
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		node2 = slow.next
		slow.next = None
		node2 = self.reverseList(node2)
		merge_list = node(0)
		cur = merge_list
		node1 = head
		while node1 != None or node2 != None:
			if node1 != None:
				cur.next = node1
				cur = cur.next
				node1 = node1.next
			if node2 != None:
				cur.next = node2
				cur = cur.next
				node2 = node2.next
		merge_list = merge_list.next


class node:

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

class Linked_List:

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

class Solution:

	def reverse(self, h):
		if not h or not h.next:
			return h
		ptr = None
		while h:
			temp = h.next
			h.next = ptr
			ptr = h
			h = temp
		return ptr

	def rex(self, head):
		if not head or not head.next:
			return None
		slow = head
		fast = head.next
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		if fast.next:
			slow = slow.next
		ex = slow.next
		slow.next = None
		return ex

	def reorderList(self, head):
		h = self.rex(head)
		h = self.reverse(h)
		p = head
		while h:
			x = h.next
			h.next = p.next
			p.next = h
			p = p.next.next
			h = x
		return head


class node:

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

class Linked_List:

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

class Solution:

	def cutinhalf(self, head):
		if not head or not head.next:
			return None
		(slow, fast) = (head, head.next)
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		if fast.next:
			slow = slow.next
		t = slow.next
		slow.next = None
		return t

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

	def reorderList(self, head):
		head2 = self.cutinhalf(head)
		head2 = self.reverse(head2)
		ptr = head
		while head2:
			x = head2.next
			head2.next = ptr.next
			ptr.next = head2
			ptr = ptr.next.next
			head2 = x
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head.next == None:
			return head
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		l1 = slow.next
		slow.next = None
		prev = None
		later = None
		while l1:
			later = l1.next
			l1.next = prev
			prev = l1
			l1 = later
		(head1, head2) = (head, prev)
		while head1 and head2:
			nextt = head1.next
			head1.next = head2
			head1 = head2
			head2 = nextt
		return head1


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		ptr = head
		lst = []
		while ptr:
			lst.append(ptr.data)
			ptr = ptr.next
		i = 0
		j = len(lst) - 1
		check = True
		ptr = head
		while ptr:
			if check == True:
				ptr.data = lst[i]
				i += 1
				check = False
			else:
				ptr.data = lst[j]
				j -= 1
				check = True
			ptr = ptr.next


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		temp = head
		op = []
		while temp:
			op.append(temp.data)
			temp = temp.next
		temp = head
		i = 0
		j = len(op) - 1
		while i <= j and temp:
			temp.data = op[i]
			if temp.next:
				temp.next.data = op[j]
			if temp.next and temp.next.next:
				temp = temp.next.next
			i += 1
			j -= 1
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head == None or head.next == None or head.next.next == None:
			return head
		slow = fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		h2 = slow.next
		slow.next = None
		current = h2
		nxt = current.next
		current.next = None
		while nxt:
			tmp = nxt.next
			nxt.next = current
			current = nxt
			nxt = tmp
		h2 = current
		h1 = head
		while h1 and h2:
			tmp = h1.next
			h1.next = h2
			h1 = h2
			h2 = tmp
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if not head or not head.next:
			return head

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

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

		def mergeLists(head1, head2):
			head = head1
			while head2:
				(head1Next, head2Next) = (head1.next, head2.next)
				head2.next = head1.next
				head1.next = head2
				head1 = head1Next
				head2 = head2Next
			return head
		mid = getMid(head)
		(left, right) = (head, mid.next)
		right = reverse(right)
		mid.next = None
		return mergeLists(left, right)


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		start = node(0)
		start.next = head
		n = 0
		while head:
			n += 1
			head = head.next
		head = start.next
		for _ in range(n // 2):
			head = head.next
		head2 = head.next
		head.next = None
		temp1 = None
		while head2:
			temp2 = head2.next
			head2.next = temp1
			temp1 = head2
			head2 = temp2
		head2 = temp1
		head1 = start.next
		while head1 and head2:
			temp = head1.next
			head1.next = head2
			head1 = temp
			temp = head2.next
			head2.next = head1
			head2 = temp
		return start.next


class Solution:

	def reverse(self, h):
		if not h or not h.next:
			return h
		ptr = None
		while h:
			temp = h.next
			h.next = ptr
			ptr = h
			h = temp
		return ptr

	def rex(self, head):
		if not head or not head.next:
			return None
		slow = head
		fast = head.next
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		if fast.next:
			slow = slow.next
		ex = slow.next
		slow.next = None
		return ex

	def reorderList(self, head):
		h = self.rex(head)
		h = self.reverse(h)
		p = head
		while h:
			x = h.next
			h.next = p.next
			p.next = h
			p = p.next.next
			h = x
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		t = []
		s = []
		temp = head
		while temp != None:
			s.append(temp.data)
			temp = temp.next
		for i in range(len(s) // 2):
			t.extend([s[i], s[n - i - 1]])
		t.append(s[len(s) // 2])
		k = 0
		temp = head
		while temp != None:
			temp.data = t[k]
			k += 1
			temp = temp.next
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):

		def rev(head):
			prev = None
			cur = head
			while cur:
				nxt = cur.next
				cur.next = prev
				prev = cur
				cur = nxt
			return prev
		ptr = head
		n = 0
		while ptr:
			n += 1
			ptr = ptr.next
		mid = (n - 1) // 2
		ptr = head
		while mid:
			mid -= 1
			ptr = ptr.next
		lst2 = ptr.next
		lst2 = rev(lst2)
		ptr.next = None
		lst1 = head
		ind = 0
		(ptr1, ptr2) = (lst1, lst2)
		ans = node(-1)
		while ptr1 and ptr2:
			if ind % 2 == 0:
				ans.next = ptr1
				ans = ans.next
				ptr1 = ptr1.next
			else:
				ans.next = ptr2
				ans = ans.next
				ptr2 = ptr2.next
			ind += 1
		while ptr1:
			ans.next = ptr1
			ans = ans.next
			ptr1 = ptr.next
			ind += 1
		while ptr2:
			ans.next = ptr2
			ans = ans.next
			ptr2 = ptr2.next
			ind += 1


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		l = []
		v = head
		if head == None and head.next == None:
			return head
		while head != None:
			l.append(head.data)
			head = head.next
		a = l[0:len(l) // 2]
		b = l[len(l) // 2:]
		b = b[-1::-1]
		c = []
		for i in range(0, len(l) // 2):
			c.append(a[i])
			c.append(b[i])
		if len(l) % 2 != 0:
			c.append(l[len(l) // 2])
		head = v
		y = head
		for i in range(1, len(c)):
			z = node(c[i])
			y.next = z
			y = z
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		arr = []
		curr = head
		while curr:
			arr.append(curr.data)
			curr = curr.next
		n = len(arr)
		ans = [0] * n
		j = n - 1
		i = 0
		c = 0
		while c < n:
			if c % 2 == 0:
				ans[c] = arr[i]
				i += 1
			else:
				ans[c] = arr[j]
				j -= 1
			c += 1
		curr = head
		for i in ans:
			curr.data = i
			curr = curr.next


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):

		def rev(sub):
			prev = None
			while sub:
				temp = sub.next
				sub.next = prev
				prev = sub
				sub = temp
			return prev
		slow = head
		fast = head
		temp = head
		while slow != None:
			if fast.next == None or fast.next.next == None:
				slow = slow.next
				temp.next = None
				break
			temp = temp.next
			slow = slow.next
			fast = fast.next.next
		r = rev(slow)
		p = head
		while r:
			h = r.next
			r.next = p.next
			p.next = r
			p = p.next.next
			r = h
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		l = []
		curr = head
		while curr != None:
			l.append(curr.data)
			curr = curr.next
		l1 = []
		s = 0
		e = len(l) - 1
		while s <= e:
			if s == e:
				l1.append(l[s])
				break
			l1.append(l[s])
			l1.append(l[e])
			s += 1
			e -= 1
		cnt = 0
		curr = head
		while curr != None:
			curr.data = l1[cnt]
			cnt += 1
			curr = curr.next
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):

		def reverseLL(head):
			cur = head
			temp = head
			prev = None
			while cur:
				cur = cur.next
				temp.next = prev
				prev = temp
				temp = cur
			return prev
		firstHalf = head
		fast = head
		slow = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		secondHalf = slow.next
		slow.next = None
		secondHalfRev = reverseLL(secondHalf)
		fh = firstHalf
		res = fh
		sh = secondHalfRev
		while sh:
			temp1 = fh.next
			temp2 = sh.next
			fh.next = sh
			sh.next = temp1
			fh = temp1
			sh = temp2
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		stack = []
		temp = head
		c = 0
		while temp:
			stack.append(temp.data)
			c += 1
			temp = temp.next
		i = 0
		j = c - 1
		while i < j:
			head.data = stack[i]
			head = head.next
			head.data = stack[j]
			head = head.next
			i += 1
			j -= 1
		if c & 1:
			head.data = stack[i]


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, 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)


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		count = self.Count(head)
		odd = 0
		even = 0
		i = 0
		if count % 2 != 0:
			i = int(count / 2) + 1
		else:
			i = int(count / 2)
		first = second = None
		h = head
		pre = None
		while i > 0:
			if not first:
				first = h
			pre = h
			h = h.next
			i -= 1
		second = h
		pre.next = None
		second = self.reverseList(second)
		return self.Get(first, second)

	def Count(self, head):
		count = 0
		while head:
			count += 1
			head = head.next
		return count

	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 Get(self, first, second):
		head1 = first
		pre = None
		while first and second:
			if pre:
				pre.next = first
			Next1 = first.next
			Next2 = second.next
			first.next = second
			pre = second
			second.next = None
			first = Next1
			second = Next2
		if first and pre:
			pre.next = first
		return head1


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if not head or not head.next:
			return head
		slow = fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		second_half = slow.next
		slow.next = None
		prev = None
		curr = second_half
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		second_half = prev
		p1 = head
		p2 = second_half
		while p2:
			next_p1 = p1.next
			next_p2 = p2.next
			p1.next = p2
			p2.next = next_p1
			p1 = next_p1
			p2 = next_p2
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		(slow, fast) = (head, head.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 = head
		while cur and prev:
			n1 = cur.next
			n2 = prev.next
			cur.next = prev
			prev.next = n1
			cur = n1
			prev = n2
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		l = 1
		temp = head
		while head:
			l += 1
			head = head.next
		head = temp
		l = l // 2
		while head:
			l -= 1
			if l == 0:
				val = head.next
				head.next = None
				break
			head = head.next
		prev = None
		curr = val
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		key = temp
		while prev:
			n1 = node(prev.data)
			n2 = temp.next
			temp.next = n1
			temp = temp.next
			temp.next = n2
			prev = prev.next
			temp = temp.next
		return key


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):

		def reverse(head):
			curr = head
			prev = None
			forward = None
			while curr != None:
				forward = curr.next
				curr.next = prev
				prev = curr
				curr = forward
			return prev
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		node1 = head
		node2 = slow.next
		slow.next = None
		node2 = reverse(node2)
		head = node(0)
		curr = head
		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
		head = head.next
		return node


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		(fast, slow) = (head, head)
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		prev = None
		while slow:
			nextt = slow.next
			slow.next = prev
			prev = slow
			slow = nextt
		temp = head
		while prev and temp:
			fNext = temp.next
			temp.next = prev
			temp = fNext
			sNext = prev.next
			prev.next = temp
			prev = sNext
		if temp is not None:
			temp.next = None


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		p = head
		length = 0
		L = []
		if p is None:
			return head
		if p.next is None:
			return head
		while p is not None:
			length += 1
			p = p.next
		p = head
		for i in range(1, length + 1):
			if i > int(length / 2) + 1:
				L.append(p)
			p = p.next
		L.reverse()
		for x in L:
			x.next = None
		p = head
		for i in range(1, int(length / 2) + 1):
			p = p.next
		p.next = None
		p = head
		for x in L:
			x.next = p.next
			p.next = x
			p = p.next.next
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head.next == None:
			return head
		fast = head
		slow = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		b = slow
		slow = slow.next
		b.next = None
		prev = None
		while slow:
			a = slow.next
			slow.next = prev
			prev = slow
			slow = a
		a = head
		while a and prev:
			b = a.next
			a.next = prev
			prev = prev.next
			a.next.next = b
			a = b
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(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:
			return head
		slow = head
		fast = head
		while fast.next != None and fast.next.next != None:
			slow = slow.next
			fast = fast.next.next
		newHead = slow.next
		slow.next = None
		newHead = reverseList(newHead)
		curr1 = head
		while newHead != None:
			nex = curr1.next
			nex2 = newHead.next
			curr1.next = newHead
			newHead.next = nex
			curr1 = nex
			newHead = nex2
		return head


class node:

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

class Linked_List:

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

class Solution:

	def middleNode(self, head):
		p = head
		q = head
		while q is not None and q.next is not None:
			p = p.next
			q = q.next.next
		return p

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

	def reorderList(self, head):
		if head.next is None:
			return head
		middle = self.middleNode(head)
		rev_head = self.reverseList(middle)
		first = head
		second = rev_head
		while second.next is not None:
			temp1 = first.next
			first.next = second
			first = temp1
			temp2 = second.next
			second.next = first
			second = temp2
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head.next == None:
			return head

		def middle(head):
			hare = head
			tur = head
			while hare != None and hare.next != None:
				tur = tur.next
				hare = hare.next.next
			return tur

		def reverse(head):
			prev = None
			curr = head
			while curr:
				nex = curr.next
				curr.next = prev
				prev = curr
				curr = nex
			return prev
		rtemp = reverse(middle(head))
		rnext = rtemp.next
		htemp = head
		hnext = htemp.next
		while rnext != None:
			htemp.next = rtemp
			rtemp.next = hnext
			htemp = hnext
			rtemp = rnext
			hnext = htemp.next
			rnext = rtemp.next
		return head


class Solution:

	def reorderList(self, head):
		fast = slow = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		t2 = slow.next
		slow.next = None
		prev = None
		while t2:
			nxt = t2.next
			t2.next = prev
			prev = t2
			t2 = nxt
		current1 = head
		current2 = prev
		while current1 and current2:
			next1 = current1.next
			next2 = current2.next
			current1.next = current2
			current2.next = next1
			current1 = next1
			current2 = next2


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if not head:
			return
		p1 = head
		c1 = 1
		while p1.next:
			c1 += 1
			p1 = p1.next
		val = c1
		if c1 % 2 == 0:
			c1 = c1 // 2 - 1
		else:
			c1 = c1 // 2
		p2 = head
		for i in range(c1):
			p2 = p2.next
		prev = None
		cur = p2.next
		while cur:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
		p2.next = prev
		p1 = head
		p2 = head
		p3 = head
		for i in range(c1 + 1):
			p2 = p2.next
		for i in range(c1):
			p3 = p3.next
			hal = p3.data
		while p2:
			n1 = p1.next
			n2 = p2.next
			p1.next = p2
			if p2.next:
				p2.next = n1
			p1 = n1
			p2 = n2
		if val % 2 != 0 and val > 2:
			vat = head
			for i in range(val - 2):
				vat = vat.next
			vat.next = node(hal)
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		fast = slow = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		t2 = slow.next
		slow.next = None
		prev = None
		while t2:
			nxt = t2.next
			t2.next = prev
			prev = t2
			t2 = nxt
		current1 = head
		current2 = prev
		while current1 and current2:
			next1 = current1.next
			next2 = current2.next
			current1.next = current2
			current2.next = next1
			current1 = next1
			current2 = next2


class node:

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

class Linked_List:

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

class Solution:

	def lreverse(self, listt):
		prev = None
		current = listt
		while current is not None:
			nextNode = current.next
			current.next = prev
			prev = current
			current = nextNode
		listt = prev
		return listt

	def reorderList(self, head):
		if head == None or head.next == None:
			return head
		(slow, fast) = (head, head.next)
		prevslow = None
		while fast.next and fast.next.next:
			prevslow = slow
			fast = fast.next.next
			slow = slow.next
		if fast.next:
			slow = slow.next
			fast = fast.next
		listt = self.lreverse(slow.next)
		slow.next = None
		first = head
		second = listt
		while first and second:
			temp1 = first.next
			temp2 = second.next
			first.next = second
			second.next = temp1
			first = temp1
			second = temp2
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		if head == None or head.next == None:
			return

		def reverse(head):
			prev = None
			curr = head
			while curr:
				next_ = curr.next
				curr.next = prev
				prev = curr
				curr = next_
			return prev
		slow = head
		fast = head
		prev = head
		while fast != None and fast.next != None:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		prev.next = None
		l1 = head
		l2 = reverse(slow)
		while l2 != None:
			next_ = l1.next
			l1.next = l2
			l1 = l2
			l2 = next_
		return head


class node:

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

class Linked_List:

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

class Solution:

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

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

	def reorderList(self, head):
		mid = self.find_mid(head)
		left = head
		right = self.reverse(mid.next)
		mid.next = None
		while right:
			next = left.next
			left.next = right
			left = right
			right = next
		return head


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		li = []
		temp = head
		while temp:
			li.append(temp.data)
			temp = temp.next
		l1 = []
		i = 0
		n = len(li)
		while i < n // 2:
			l1.append(li[i])
			l1.append(li[n - i - 1])
			i += 1
		if n % 2 == 1:
			l1.append(li[n // 2])
		temp = head
		for i in range(n):
			temp.data = l1[i]
			temp = temp.next
		return head
		pass


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		temp = head
		l = []
		while temp:
			l.append(temp.data)
			temp = temp.next
		boolean = True
		m = 0
		n = -1
		temp = head
		while temp:
			if boolean:
				temp.data = l[m]
				m += 1
				boolean = False
			else:
				temp.data = l[n]
				n -= 1
				boolean = True
			temp = temp.next
		return head


class node:

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

class Linked_List:

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

class Solution:

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

	def getEndToMiddle(self, middle, head):
		tmp = head
		newList = None
		newListHead = None
		ctr = 1
		while tmp.next:
			tmp = tmp.next
			ctr += 1
			if ctr >= middle:
				if not newList:
					newList = node(tmp)
					newListHead = newList
				else:
					newList.next = node(tmp)
					newList = newList.next
		rev = self.reverseLL(newListHead)
		return rev

	def reorderList(self, head):
		tmp = head
		n = 0
		while tmp:
			n += 1
			tmp = tmp.next
		middle = n // 2
		rev = self.getEndToMiddle(middle, head)
		tmp = head
		ctr = 0
		while ctr < middle:
			s = rev
			rev = rev.next
			s.data.next = tmp.next
			tmp.next = s.data
			ctr += 1
			tmp = tmp.next.next
		if n % 2 == 0:
			tmp.next.next = None
		else:
			tmp.next = None


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		second = slow.next
		slow.next = None
		prev = None
		while second:
			next1 = second.next
			second.next = prev
			prev = second
			second = next1
		second = prev
		cur = head
		while cur and second:
			next1 = second.next
			next2 = cur.next
			cur.next = second
			cur = next2
			second.next = cur
			second = next1


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		(slow, fast) = (head, head)
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		second = self.reverse(slow.next)
		prev = slow.next = None
		first = head
		while second:
			(ptr1, ptr2) = (first.next, second.next)
			first.next = second
			second.next = ptr1
			(first, second) = (ptr1, ptr2)
		return head

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


class node:

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

class Linked_List:

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

class Solution:

	def reorderList(self, head):
		n = 0
		temp = head
		while temp:
			n += 1
			temp = temp.next
		mid = 0
		if n & 1:
			mid = n // 2
		else:
			mid = n // 2 - 1
		temp = head
		pprev = head
		while mid >= 0:
			pprev = temp
			temp = temp.next
			mid -= 1
		pprev.next = None
		prev = None
		while temp:
			next = temp.next
			temp.next = prev
			prev = temp
			temp = next
		temp = head
		while prev:
			t_next = temp.next
			p_next = prev.next
			temp.next = prev
			prev.next = t_next
			temp = t_next
			prev = p_next
		return head