Given a singly linked list of size N. Your task is to complete the function alternatingSplitList() that splits the given linked list into two smaller list. The sublists should be made from alternating elements from the original list.
Note: the sublist should in the order with respect to original list.
Input Format:
First line of input contains number of testcaes T. First line of each input contains length of the linked list and next line contains the elements of the linked list.
Output Format:
For each test case, in new lines, print the two sublists formed after the split.
User Task:
The task is to complete the function alternatingSplitList() which takes the head as parameter and splits the lists into two. The head of the first list should be stored in the provided variable a, and the head of the second should be stored in the provided variable b. The printing is done by the driver code.
Constraints:
1 <= T <= 100
1 <= N <= 100
Example:
Input:
2
6
0 1 0 1 0 1
5
2 5 8 9 6
Output:
0 0 0
1 1 1
2 8 6
5 9
Explanation:
Testcase 1: After forming two sublists of the given list as required, we have two lists as: 0->0->0 and 1->1->1.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None



'''



'''

These are global variables to store heads of split lists

a --- store head of first list

b --- store head of second list

'''



def alternatingSplitList(head):

    global a,b

    #Your code here

Solutions:
def alternatingSplitList(head):
	global a, b
	if not head or not head.next:
		(a, b) = (head, head)
	(a, b) = (head, head.next)
	(ptr1, ptr2) = (head, head.next)
	while ptr1 and ptr2:
		ptr1.next = ptr2.next
		ptr1 = ptr1.next
		ptr2.next = ptr1.next if ptr1 else None
		ptr2 = ptr2.next

	def reverse(head):
		if not head or not head.next:
			return head
		(prev, cur, nxt) = (None, head, head.next)
		while cur:
			cur.next = prev
			prev = cur
			cur = nxt
			nxt = cur.next if cur else None
		return prev
	(a, b) = (reverse(a), reverse(b))


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

def alternatingSplitList(head):
	global a, b
	temp1 = tmp1 = None
	temp2 = tmp2 = None
	i = 0
	while head:
		if not i % 2:
			if not temp1:
				tmp1 = head
				temp1 = head
			else:
				temp1.next = head
				temp1 = temp1.next
		elif not temp2:
			tmp2 = head
			temp2 = head
		else:
			temp2.next = head
			temp2 = temp2.next
		head = head.next
		i += 1
	if temp1:
		temp1.next = None
	if temp2:
		temp2.next = None
	a = reverse(tmp1)
	b = reverse(tmp2)


def alternatingSplitList(head):
	global a, b
	current = head
	while current is not None:
		a = append(a, current.data)
		current = current.next
		if current is not None:
			b = append(b, current.data)
			current = current.next


class Node:

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

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

def alternatingSplitList(head):
	global a, b
	temp1 = tmp1 = None
	temp2 = tmp2 = None
	i = 0
	while head:
		if not i % 2:
			if not temp1:
				tmp1 = head
				temp1 = head
			else:
				temp1.next = head
				temp1 = temp1.next
		elif not temp2:
			tmp2 = head
			temp2 = head
		else:
			temp2.next = head
			temp2 = temp2.next
		head = head.next
		i += 1
	if temp1:
		temp1.next = None
	if temp2:
		temp2.next = None
	a = reverse(tmp1)
	b = reverse(tmp2)


def alternatingSplitList(head):
	global a, b
	aa = []
	bb = []
	c = 0
	while head is not None:
		if c % 2 == 0:
			aa.append(head.data)
		else:
			bb.append(head.data)
		c = c + 1
		head = head.next
	aa = aa[::-1]
	bb = bb[::-1]
	aa.append('x')
	a = None
	taila = None
	for ele in aa:
		if ele != 'x':
			if a is None:
				newnode = Node(ele)
				a = newnode
				tail = newnode
			else:
				newnode = Node(ele)
				tail.next = newnode
				tail = newnode
	bb.append('x')
	b = None
	tail = None
	for ele in bb:
		if ele != 'x':
			if b is None:
				newnode = Node(ele)
				b = newnode
				tail = newnode
			else:
				newnode = Node(ele)
				tail.next = newnode
				tail = newnode
	return (a, b)


def alternatingSplitList(head):
	global a, b
	t = head
	c = 0
	l1 = []
	l2 = []
	if t.next == None:
		a = head
		return (a, b)
	while t:
		if c % 2 == 0:
			l1.append(t.data)
			c += 1
		else:
			l2.append(t.data)
			c += 1
		t = t.next
	a = Node(l1[0])
	l1.remove(l1[0])
	b = Node(l2[0])
	l2.remove(l2[0])
	for item in l1:
		node = Node(item)
		node.next = a
		a = node
	for item in l2:
		node = Node(item)
		node.next = b
		b = node
	return (a, b)


def alternatingSplitList(head):
	global a, b
	arr = [None, None]
	while head:
		arr.append(head)
		head = head.next
	items_a = arr[::2]
	items_b = arr[1::2]
	a = items_a[-1]
	b = items_b[-1]
	for i in range(len(items_a) - 1):
		items_a[-i - 1].next = items_a[-i - 2]
	for i in range(len(items_b) - 1):
		items_b[-i - 1].next = items_b[-i - 2]


def alternatingSplitList(head):
	global a, b
	temp = head
	bool = 1
	while temp:
		if bool:
			a = append(a, temp.data)
			bool = 0
		else:
			bool = 1
			b = append(b, temp.data)
		temp = temp.next


def alternatingSplitList(head):
	global a, b
	p = head
	l1 = []
	l2 = []
	n = 1
	while p:
		if n % 2 == 0:
			l2.append(p.data)
		else:
			l1.append(p.data)
		p = p.next
		n += 1
	dummy1 = Node(0)
	n1 = dummy1
	dummy2 = Node(0)
	n2 = dummy2
	l1.reverse()
	l2.reverse()
	for i in l1:
		n1.next = Node(i)
		n1 = n1.next
	for i in l2:
		n2.next = Node(i)
		n2 = n2.next
	(a, b) = (dummy1.next, dummy2.next)
	return (a, b)


def alternatingSplitList(head):
	global a, b
	temp1 = None
	temp2 = None
	i = 0
	while head:
		nextt = head.next
		if i % 2 == 0:
			head.next = temp1
			temp1 = head
		else:
			head.next = temp2
			temp2 = head
		head = nextt
		i += 1
	a = temp1
	b = temp2


def alternatingSplitList(head):
	global a, b
	n = head
	aa = None
	a = None
	bb = None
	b = None
	count = 0
	while n != None:
		if count % 2 == 0:
			if a == None:
				a = n
				aa = n
			else:
				aa.next = n
				aa = aa.next
		elif count % 2 != 0:
			if b == None:
				b = n
				bb = n
			else:
				bb.next = n
				bb = bb.next
		count += 1
		n = n.next
	if bb != None:
		bb.next = None
	if aa != None:
		aa.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
	a = reverse(a)
	b = reverse(b)
	return (a, b)


def alternatingSplitList(head):
	global a, b
	head1 = None
	tail1 = None
	head2 = None
	tail2 = None
	temp = head
	c = 0
	while temp:
		if c % 2 == 0:
			if head1 == None:
				n = Node(temp.data)
				head1 = n
			else:
				n = Node(temp.data)
				n.next = head1
				head1 = n
		elif head2 == None:
			n = Node(temp.data)
			head2 = n
		else:
			n = Node(temp.data)
			n.next = head2
			head2 = n
		temp = temp.next
		c += 1
	a = head1
	b = head2


def alternatingSplitList(head):
	global a, b
	temp1 = head
	(fp, sp) = (None, None)
	(k, l) = ([], [])
	while temp1:
		fp = Node(temp1.data)
		k.append(fp)
		if temp1.next:
			sp = Node(temp1.next.data)
			l.append(sp)
		if temp1.next:
			temp1 = temp1.next.next
		else:
			break
	if len(k) == 1:
		a = k[0]
	if len(l) == 1:
		b = l[0]
	for i in range(len(k) - 1, -1, -1):
		if i == 0:
			k[i].next = None
		elif i == len(k) - 1:
			a = k[i]
			k[i].next = k[i - 1]
		else:
			k[i].next = k[i - 1]
	for j in range(len(l) - 1, -1, -1):
		if j == 0:
			l[j].next = None
		elif j == len(l) - 1:
			b = l[j]
			l[j].next = l[j - 1]
		else:
			l[j].next = l[j - 1]


def alternatingSplitList(head):
	global a, b
	a = head
	a1 = a
	t = head.next
	b = None
	if t != None:
		t = t.next
		b = head.next
		b1 = b
		while t != None:
			a1.next = t
			a1 = a1.next
			t = t.next
			if t != None:
				b1.next = t
				b1 = b1.next
				t = t.next
		a1.next = None
		b1.next = None
		a1 = a
		d = None
		while a1 != None:
			n = a1.next
			a1.next = d
			d = a1
			a1 = n
		a = d
		d = None
		b1 = b
		while b1 != None:
			n = b1.next
			b1.next = d
			d = b1
			b1 = n
		b = d
	return (b, a)


def alternatingSplitList(head):
	global a, b
	c1 = None
	c2 = None
	i = 0
	while head:
		n = head.next
		if i % 2 == 0:
			head.next = c1
			c1 = head
		else:
			head.next = c2
			c2 = head
		head = n
		i += 1
	a = c1
	b = c2


def alternatingSplitList(head):
	global a, b
	x = []
	y = []
	count = 0
	temp = head
	temp1 = head
	while temp is not None:
		count += 1
		temp = temp.next
	for i in range(count):
		if i % 2 == 0:
			x.append(temp1.data)
			temp1 = temp1.next
		else:
			y.append(temp1.data)
			temp1 = temp1.next
	for item in x[:]:
		new_node = Node(item)
		if a is None:
			a = new_node
			new_node.next = None
		else:
			new_node.next = a
			a = new_node
	for item in y[:]:
		new_node = Node(item)
		if b is None:
			b = new_node
			new_node.next = None
		else:
			new_node.next = b
			b = new_node


def alternatingSplitList(head):
	global a, b
	l = []
	l1 = []
	l2 = []
	i = 0
	temp = head
	if head is None or head.next is None:
		a = head
	else:
		while temp:
			if i % 2 == 0:
				l1.append(temp.data)
				temp = temp.next
			else:
				l2.append(temp.data)
				temp = temp.next
			i += 1
		a = Node(l1[0])
		b = Node(l2[0])
		for item in l1[1:]:
			new_node = Node(item)
			if a is None:
				a = new_node
				new_node.next = None
			else:
				new_node.next = a
				a = new_node
		for item in l2[1:]:
			new_node = Node(item)
			if b is None:
				b = new_node
				new_node.next = None
			else:
				new_node.next = b
				b = new_node


def alternatingSplitList(head):
	global a, b
	temp1 = None
	temp2 = None
	i = 0
	while head:
		x = head.next
		if i & 1 == 0:
			head.next = temp1
			temp1 = head
		else:
			head.next = temp2
			temp2 = head
		head = x
		i += 1
	a = temp1
	b = temp2


def reverse(head):
	if head == None or head.next == None:
		return head
	else:
		rev = reverse(head.next)
		head.next.next = head
		return rev

def printt(head1):
	while head1:
		print(head1.data, end=' ')
		head1 = head1.next
	print()

def alternatingSplitList(head):
	global a, b
	n = reverse(head)
	head.next = None
	head = n
	if head == None or head.next == None:
		a = head
		b = None
		return
	head1 = head
	head2 = head.next
	headd = head.next.next
	cur1 = head1
	cur2 = head2
	i = 0
	n = 2
	while headd != None:
		if i % 2 == 0:
			cur1.next = headd
			cur1 = cur1.next
		else:
			cur2.next = headd
			cur2 = cur2.next
		headd = headd.next
		n += 1
		i += 1
	cur1.next = None
	cur2.next = None
	a = head1
	b = head2
	if n % 2 == 0:
		(a, b) = (b, a)


def alternatingSplitList(head):
	global a, b
	l = []
	p = head
	while p:
		l.append(p.data)
		p = p.next
	a = Node(l[0])
	if len(l) == 1:
		return
	for i in l[2:len(l):2]:
		p = Node(i)
		p.next = a
		a = p
	b = Node(l[1])
	for i in l[3:len(l):2]:
		p = Node(i)
		p.next = b
		b = p


def alternatingSplitList(head):
	global a, b
	j = []
	m = []
	k = []
	itr = head
	while itr:
		j.append(itr.data)
		itr = itr.next
	for i in range(len(j) - 1, -1, -1):
		if i % 2 == 0:
			m.append(j[i])
		else:
			k.append(j[i])
	ans = pre = Node(-1)
	an = pr = Node(-1)
	for i in range(len(m)):
		pre.next = Node(m[i])
		pre = pre.next
	for i in range(len(k)):
		pr.next = Node(k[i])
		pr = pr.next
	a = ans.next
	b = an.next
	return (a, b)


def alternatingSplitList(head):
	global a, b
	if head.next is None:
		a = head
		return
	l = []
	while head:
		l.append(head)
		head = head.next
	c = l[0::2]
	d = l[1::2]
	c = c[::-1]
	d = d[::-1]
	m = len(c)
	for i in range(m - 1):
		c[i].next = c[i + 1]
	c[-1].next = None
	n = len(d)
	for i in range(n - 1):
		d[i].next = d[i + 1]
	d[-1].next = None
	a = c[0]
	b = d[0]


def alternatingSplitList(head):
	global a, b
	temp = head
	if head == None or head.next == None:
		a = head
		b = None
		return head
	i = 0
	evens = []
	odds = []
	while temp != None:
		if i % 2 == 0:
			evens.append(temp)
		else:
			odds.append(temp)
		i += 1
		temp = temp.next
	evens.reverse()
	odds.reverse()
	a = evens[0]
	b = odds[0]
	for i in range(len(evens) - 1):
		evens[i].next = evens[i + 1]
	evens[-1].next = None
	for i in range(len(odds) - 1):
		odds[i].next = odds[i + 1]
	odds[-1].next = None
	return

class Node:

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

def printList(head):
	temp = head
	while temp:
		print(temp.data, end=' ')
		temp = temp.next
	print()
a = None
b = None

def append(head, data):
	new_node = Node(data)
	if head is None:
		head = new_node
	else:
		new_node.next = head
		head = new_node
	return head
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		head = None
		a = None
		b = None
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in values:
			head = append(head, i)
		alternatingSplitList(head)
		if n % 2 is 0:
			(a, b) = (b, a)
		printList(a)
		printList(b)
		t -= 1


def alternatingSplitList(head):
	global a, b
	curr = head
	next = None
	i = 1
	while curr != None:
		next = curr.next
		if i % 2 != 0:
			if a == None:
				a = curr
				a.next = None
			else:
				curr.next = a
				a = curr
		elif b == None:
			b = curr
			b.next = None
		else:
			curr.next = b
			b = curr
		curr = next
		i += 1


def alternatingSplitList(head):
	global a, b
	p = head
	f = 1
	(a, b) = (None, None)
	if p:
		a = p
		la = p
	else:
		return
	p = p.next
	if p:
		b = p
		lb = p
	else:
		return
	p = p.next
	(m, n) = (a, b)
	while p != None:
		if f > 0:
			m = p
			p = p.next
			m.next = a
			a = m
		else:
			n = p
			p = p.next
			n.next = b
			b = n
		f *= -1
	la.next = None
	lb.next = None


def alternatingSplitList(head):
	c = head
	ah = None
	at = None
	bh = None
	bt = None
	cnt = 0
	global a, b
	while c:
		if cnt % 2 == 0:
			if ah is None:
				ah = Node(c.data)
				at = ah
			else:
				n = Node(c.data)
				n.next = ah
				ah = n
		elif bh is None:
			bh = Node(c.data)
			bt = bh
		else:
			n = Node(c.data)
			n.next = bh
			bh = n
		cnt += 1
		c = c.next
	a = ah
	b = bh


def alternatingSplitList(head):
	global a, b
	odd = None
	even = None
	cur = head
	while cur:
		if not odd:
			odd = Node(cur.data)
		else:
			temp = Node(cur.data)
			temp.next = odd
			odd = temp
		cur = cur.next
		if cur:
			if not even:
				even = Node(cur.data)
			else:
				temp = Node(cur.data)
				temp.next = even
				even = temp
			cur = cur.next
	a = odd
	b = even


def alternatingSplitList(head):
	global a, b
	arr = []
	brr = []
	curr = head
	c = 0
	while curr != None:
		c += 1
		if c % 2 != 0:
			arr.append(curr.data)
		else:
			brr.append(curr.data)
		curr = curr.next
	arr.reverse()
	brr.reverse()
	curr = head
	prev = None
	for i in range(0, len(arr)):
		curr.data = arr[i]
		prev = curr
		curr = curr.next
	prev.next = None
	head1 = curr
	for i in range(0, len(brr)):
		curr.data = brr[i]
		curr = curr.next
	a = head
	b = head1


def alternatingSplitList(head):
	global a, b
	if not head.next:
		a = head
		b = None
		return
	fll = head
	sll = head.next
	pfll = None
	psll = None
	while True:
		if not sll.next:
			fll.next = pfll
			sll.next = psll
			break
		fll.next = pfll
		pfll = fll
		fll = sll.next
		if not fll.next:
			sll.next = psll
			fll.next = pfll
			break
		sll.next = psll
		psll = sll
		sll = fll.next
	a = fll
	b = sll
	return


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

def alternatingSplitList(head):
	global a, b
	p = None
	q = None
	i = 0
	while head:
		nt = head.next
		if i % 2 == 0:
			head.next = p
			p = head
		else:
			head.next = q
			q = head
		head = nt
		i += 1
	a = p
	b = q


def alternatingSplitList(head):
	global a, b
	head1 = None
	head2 = None
	temp = head
	temp1 = head
	count = 1
	while temp1 != None:
		temp = temp1
		temp1 = temp1.next
		if count % 2 == 1:
			temp.next = head1
			head1 = temp
		else:
			temp.next = head2
			head2 = temp
		count += 1
	a = head1
	b = head2


def alternatingSplitList(head):
	global a, b
	tmp = head
	head1 = None
	head2 = None
	idx = 0
	while tmp:
		nextt = tmp.next
		if idx % 2 == 0:
			tmp.next = head1
			head1 = tmp
		elif idx % 2 == 1:
			tmp.next = head2
			head2 = tmp
		tmp = nextt
		idx += 1
	a = head1
	b = head2


def join_to_a(head, a):
	temp = head
	temp2 = a
	if head.next == None:
		head = None
		if a == None:
			a = temp
		else:
			temp.next = a
			a = temp
	else:
		head = temp.next
		if a == None:
			a = temp
			a.next = None
		else:
			temp.next = a
			a = temp
	return (head, a)

def alternatingSplitList(head):
	global a, b
	a = None
	b = None
	if head.next == None:
		a = head
		return (a, b)
	else:
		temp = head
		while temp != None and temp.next != None:
			(temp, a) = join_to_a(temp, a)
			(temp, b) = join_to_a(temp, b)
		if temp != None:
			(temp, a) = join_to_a(temp, a)
	return


def alternatingSplitList(head):
	global a, b
	a = None
	b = None
	p = head
	p1 = a
	p2 = b
	if head is None:
		return
	if head.next is None:
		a = head
		return
	while p:
		if a is None:
			a = p
			b = p.next
			p = p.next.next
			a.next = None
			b.next = None
		else:
			x = p
			p = p.next
			x.next = a
			a = x
			if p:
				x = p
				p = p.next
				x.next = b
				b = x


def alternatingSplitList(head):
	global a, b
	t1 = t2 = head
	c = 1
	a = b = None
	lasta = lastb = head
	while t1:
		if c % 2 == 1:
			if a == None:
				a = Node(t1.data)
			else:
				nna = Node(t1.data)
				nna.next = a
				a = nna
			c = c + 1
			t1 = t1.next
		else:
			if b == None:
				b = Node(t1.data)
			else:
				nnb = Node(t1.data)
				nnb.next = b
				b = nnb
			c = c + 1
			t1 = t1.next


def rec_rev(head):
	if head == None or head.next == None:
		return head
	h2 = rec_rev(head.next)
	head.next.next = head
	head.next = None
	return h2

def size(head):
	counter = 0
	while head != None:
		head = head.next
		counter += 1
	return counter

def alternatingSplitList(head):
	head = rec_rev(head)
	n = size(head)
	global a, b
	if head == None:
		a = None
		b = None
		return
	a = head
	b = head.next
	ptr1 = head
	ptr2 = head.next
	while ptr1 != None and ptr1.next != None and (ptr2 != None) and (ptr2.next != None):
		ptr1.next = ptr1.next.next
		ptr2.next = ptr2.next.next
		ptr1 = ptr1.next
		ptr2 = ptr2.next
	if ptr1 != None:
		ptr1.next = None
	if ptr2 != None:
		ptr2.next = None
	if n % 2 == 0:
		(a, b) = (b, a)


def alternatingSplitList(head):
	global a, b
	index = 0
	tmp = head
	while tmp:
		if index % 2 == 0:
			new = Node(tmp.data)
			new.next = a
			a = new
		else:
			new = Node(tmp.data)
			new.next = b
			b = new
		tmp = tmp.next
		index += 1


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

def alternatingSplitList(head):
	global a, b
	ll = []
	itr = head
	cnt = 0
	while itr:
		cnt += 1
		itr = itr.next
	itr = reverse(head)
	while itr:
		ll.append(itr.data)
		itr = itr.next
	head1 = tail1 = None
	head2 = tail2 = None
	i = 0
	while i < len(ll):
		if (i + 1) % 2 != 0:
			if head1 == None:
				head1 = Node(ll[i])
				tail1 = head1
			else:
				tail1.next = Node(ll[i])
				tail1 = tail1.next
		i += 1
	j = 0
	while j < len(ll):
		if (j + 1) % 2 == 0:
			if head2 == None:
				head2 = Node(ll[j])
				tail2 = head2
			else:
				tail2.next = Node(ll[j])
				tail2 = tail2.next
		j += 1
	if cnt % 2 != 0:
		a = head1
		b = head2
	else:
		a = head2
		b = head1


def alternatingSplitList(head):
	global a, b
	start = head
	a1 = []
	a2 = []
	index = 0
	while start != None:
		if index % 2 == 0:
			a1.append(start.data)
		else:
			a2.append(start.data)
		index = index + 1
		start = start.next
	head1 = None
	head2 = None
	for i in a1:
		head1 = append(head1, i)
	for i in a2:
		head2 = append(head2, i)
	a = head1
	b = head2


def reverseList(head):
	cur = head
	prev = None
	nextNode = None
	while cur:
		nextNode = cur.next
		cur.next = prev
		prev = cur
		cur = nextNode
	return prev

def getLength(head):
	l = 0
	while head:
		l += 1
		head = head.next
	return l

def alternatingSplitList(head) -> None:
	global a, b
	if head is None:
		return
	head = reverseList(head)
	a = Node(-1)
	cura = a
	b = Node(-1)
	curb = b
	curnode = head
	i = 1
	while curnode is not None:
		if i % 2 != 0:
			cura.next = curnode
			cura = cura.next
		else:
			curb.next = curnode
			curb = curb.next
		i += 1
		curnode = curnode.next
	a = a.next
	b = b.next
	cura.next = None
	curb.next = None
	if getLength(a) == getLength(b):
		(a, b) = (b, a)


def alternatingSplitList(head):
	global a, b
	temp1 = None
	temp2 = None
	current = head
	while current is not None:
		new_node = current
		current = current.next
		new_node.next = temp1
		temp1 = new_node
		if current is not None:
			new_node = current
			current = current.next
			new_node.next = temp2
			temp2 = new_node
	a = temp1
	b = temp2
	return (a, b)


def alternatingSplitList(head):
	global a, b
	opos = []
	epos = []
	i = 0
	while head != None:
		if i % 2 == 0:
			epos.append(head.data)
		else:
			opos.append(head.data)
		head = head.next
		i += 1
	temp = dummynode = Node(0)
	epos.reverse()
	opos.reverse()
	for x in epos:
		newnode = Node(x)
		temp.next = newnode
		temp = newnode
	a = dummynode.next
	temp = dummynode = Node(0)
	for x in opos:
		newnode = Node(x)
		temp.next = newnode
		temp = newnode
	b = dummynode.next


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

def alternatingSplitList(head):
	global a, b
	if head == None:
		return head
	if head.next == None:
		a = head
		b = head.next
		return
	(p, a) = (head, head)
	(q, b) = (head.next, head.next)
	while p and q:
		if p and q:
			p.next = q.next
		if p:
			p = p.next
		if q and p:
			q.next = p.next
		if q:
			q = q.next
	a = reverse(a)
	b = reverse(b)


def alternatingSplitList(head):
	global a, b
	node1 = Node(7)
	node2 = Node(7)
	l = 0
	k = 0
	while head:
		if l == 0:
			nest = head
			node1.next = nest
			head = head.next
			nest.next = None
			l = 1
		else:
			node1.next = head
			head1 = head.next
			head.next = nest
			nest = head
			head = head1
		if not head:
			break
		if k == 0:
			nest1 = head
			node2.next = nest1
			head = head.next
			nest1.next = None
			k = 1
		else:
			node2.next = head
			head1 = head.next
			head.next = nest1
			nest1 = head
			head = head1
	a = node1.next
	b = node2.next


def reverse(head):
	if head is None:
		return
	prev = None
	current = head
	nxt = None
	while current:
		nxt = current.next
		current.next = prev
		prev = current
		current = nxt
	return prev
from collections import deque

def alternatingSplitList(head):
	global a, b
	head = reverse(head)
	d = deque([])
	prev = None
	current = head
	c = 1
	while current:
		if c % 2 == 0:
			d.append(current)
			current = current.next
			prev.next = current
			c += 1
		else:
			prev = current
			current = current.next
			c += 1
	head2 = None
	tail = None
	while d:
		if head2 is None:
			head2 = d.popleft()
			tail = head2
			tail.next = None
		else:
			tail.next = d.popleft()
			tail = tail.next
			tail.next = None
	if c % 2 == 0:
		a = head
		b = head2
	else:
		a = head2
		b = head


def alternatingSplitList(head):
	global a, b
	(a, b) = (head, head.next)
	(p, q) = (a, b)
	while q:
		(p.next, p, q) = (q.next, q, q.next)
	(prevA, prevB, curA, curB) = (None, None, a, b)
	while curA:
		nxtA = curA.next
		curA.next = prevA
		prevA = curA
		curA = nxtA
	while curB:
		nxtB = curB.next
		curB.next = prevB
		prevB = curB
		curB = nxtB
	(a, b) = (prevA, prevB)


def alternatingSplitList(head):
	global a, b
	(a, b) = (Node(0), Node(0))
	(a1, b1) = (a, b)
	ptr1 = head
	flag = 1
	while ptr1:
		if flag:
			a1.next = ptr1
			a1 = a1.next
			flag = 0
		else:
			b1.next = ptr1
			b1 = b1.next
			flag = 1
		ptr1 = ptr1.next
	(a1.next, b1.next) = (None, None)
	(a, b) = (a.next, b.next)
	(prevA, prevB, curA, curB) = (None, None, a, b)
	while curA:
		nxtA = curA.next
		curA.next = prevA
		prevA = curA
		curA = nxtA
	while curB:
		nxtB = curB.next
		curB.next = prevB
		prevB = curB
		curB = nxtB
	(a, b) = (prevA, prevB)


def alternatingSplitList(head):
	global a, b
	(a, b) = (Node(0), Node(0))
	(a1, b1) = (a, b)
	ptr = head
	while ptr:
		if ptr.next:
			(a1.next, b1.next) = (ptr, ptr.next)
			(a1, b1, ptr) = (a1.next, b1.next, ptr.next.next)
		else:
			a1.next = ptr
			a1 = a1.next
			ptr = ptr.next
	(a1.next, b1.next) = (None, None)
	(a, b) = (a.next, b.next)
	(prevA, prevB, curA, curB) = (None, None, a, b)
	while curA:
		nxtA = curA.next
		curA.next = prevA
		prevA = curA
		curA = nxtA
	while curB:
		nxtB = curB.next
		curB.next = prevB
		prevB = curB
		curB = nxtB
	(a, b) = (prevA, prevB)


def alternatingSplitList(head):
	global a, b
	if head == None or head.next == None:
		a = head
		return
	curr = head
	a = Node(head.data)
	b = Node(head.next.data)
	i = 0
	curr = head.next.next
	while curr:
		if i == 0:
			temp = Node(curr.data)
			temp.next = a
			a = temp
			i = 1
		else:
			temp = Node(curr.data)
			temp.next = b
			b = temp
			i = 0
		curr = curr.next


def alternatingSplitList(head):
	global a, b
	if head == None:
		return
	a = None
	b = None
	c = 0
	while head:
		if c % 2 == 0:
			n = Node(head.data)
			n.next = a
			a = n
			c += 1
		else:
			n = Node(head.data)
			n.next = b
			b = n
			c += 1
		head = head.next