Given two linked lists, your task is to complete the function mergeList() which inserts nodes of second list into first list at alternate positions of first list. The lists are given in the reverse order.
Constraints:
1 <= T <= 100
1 <= N <= 100
Example:
Input:
2
2
9 10
6
5 4 3 2 1 6
5
99 88 77 66 55
5
55 44 33 22 11
Output:
10 6 9 12 3 4 5
55 11 66 22 77 33 88 44 99 55
Explanation:
Testcase 1:
The two linked list are 10 -> 9 and 6 -> 1-> 2 -> 3 -> 4 -> 5
After merging the two lists as required, the new list is like: 10-> 6-> 9-> 1-> 2-> 3-> 4-> 5.
User Task:
The task is to complete the function mergeList() which should merge the two lists as required. For each test case modify the given head of the lists.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: # your task is to complete this function
# function should return a list of the
# two new heads
def mergeList(head1, head2):
    # Code here
    return [head1, head2]

Solutions:
def mergeList(head1, head2):
	if head1 and head2:
		temp1 = head1
		temp2 = head2
		while temp1 and temp2:
			b = temp1.next
			a = temp2.next
			temp1.next = temp2
			temp2.next = b
			temp1 = b
			temp2 = a
		head2 = temp2
	return [head1, head2]


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


def mergeList(head1, head2):
	(ptr1, ptr2) = (head1, head2)
	while ptr1 and ptr2:
		nxt = ptr1.next
		ptr1.next = ptr2
		ptr2 = ptr2.next
		ptr1 = ptr1.next
		ptr1.next = nxt
		ptr1 = ptr1.next
	return [head1, ptr2]


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 mergeList(head1, head2):
	pcur = head1
	qcur = head2
	pnext = None
	qnext = None
	while pcur != None and qcur != None:
		pnext = pcur.next
		qnext = qcur.next
		qcur.next = pnext
		pcur.next = qcur
		pcur = pnext
		qcur = qnext
	head2 = qcur
	return [head1, head2]


def mergeList(head1, head2):
	if head1 and head2:
		temp1 = head1
		temp2 = head2
		while temp1 and temp2:
			temp1_next = temp1.next
			temp2_next = temp2.next
			temp1.next = temp2
			temp2.next = temp1_next
			temp1 = temp1_next
			temp2 = temp2_next
		head2 = temp2
	return [head1, head2]


def mergeList(head1, head2):
	if head1 and head2:
		p_cur = head1
		q_cur = head2
		while p_cur and q_cur:
			p_n = p_cur.next
			q_n = q_cur.next
			q_cur.next = p_n
			p_cur.next = q_cur
			p_cur = p_n
			q_cur = q_n
		head2 = q_cur
	return [head1, head2]


def mergeList(head1, head2):
	_head1 = head1
	_head2 = head2
	while _head1 and head2:
		_head1_next = _head1.next
		_head2_next = _head2.next
		_head1.next = _head2
		_head2.next = _head1_next
		_head1 = _head1_next
		_head2 = _head2_next
		head2 = _head2
	return [head1, head2]


def mergeList(head1, head2):
	p1 = head1
	while p1 != None and head2 != None:
		temp = node(head2.data)
		temp.next = p1.next
		p1.next = temp
		p1 = p1.next.next
		head2 = head2.next
	return [head1, head2]


def mergeList(head1, head2):
	cur1 = head1
	cur2 = head2
	while head1 != None and head2 != None:
		next1 = head1.next
		next2 = head2.next
		head1.next = head2
		head2.next = next1
		head1 = next1
		head2 = next2
	return [cur1, head2]


def mergeList(head1, head2):
	h1 = t1 = node(None)
	h2 = t2 = node(None)
	while head1 and head2:
		t1.next = head1
		head1 = head1.next
		t1 = t1.next
		t1.next = head2
		head2 = head2.next
		t1 = t1.next
	t1.next = head1
	t2.next = head2
	return [h1.next, h2.next]


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


def mergeList(head1, head2):
	l1 = head1
	while l1.next and head2.next:
		(temp1, temp2) = (l1.next, head2.next)
		l1.next = head2
		head2.next = temp1
		head2 = temp2
		l1 = temp1
	if l1.next and (not head2.next):
		temp1 = l1.next
		l1.next = head2
		l1.next.next = temp1
		head2 = None
	elif head2.next and (not l1.next):
		l1.next = head2
		head2 = head2.next
		l1.next.next = None
	else:
		l1.next = head2
		head2 = None
	return [head1, head2]
	l1 = head1
	while l1.next and head2.next:
		(temp1, temp2) = (l1.next, head2.next)
		l1.next = head2
		head2.next = temp1
		(l1, head2) = (temp1, temp2)
	if not l1.next and head2.next:
		l1.next = head2
		head2 = head2.next
		l1.next.next = None
	elif l1.next and (not head2.next):
		temp = l1.next
		l1.next = head2
		l1.next.next = temp
		head2 = None
	else:
		l1.next = head2
		head2 = None
	return [head1, head2]


def mergeList(head1, head2):
	if head1 and head2:
		p1 = head1
		p2 = head2
		while p1 and p2:
			b = p1.next
			a = p2.next
			p1.next = p2
			p2.next = b
			p1 = b
			p2 = a
		head2 = p2
	return [head1, head2]


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

def mergeList(head1, head2):
	if head1 and head2:
		c1 = count(head1)
		c2 = count(head2)
		temp1 = head1
		temp2 = head2
		while temp1 and temp2:
			b = temp1.next
			a = temp2.next
			temp1.next = temp2
			temp2.next = b
			temp1 = b
			temp2 = a
		head2 = temp2
		return [head1, head2]


def mergeList(h1, h2):
	(s, l) = (h1, h2)
	while h1 != None and h2 != None:
		k = h1.next
		l = h2.next
		h1.next = h2
		h2.next = k
		(h1, h2) = (k, l)
	return [s, l]


def mergeList(head1, head2):
	node1 = head1
	node2 = head2
	final1 = temp1 = node(None)
	final2 = temp2 = node(None)
	while head1 and head2:
		temp1.next = head1
		head1 = head1.next
		temp1 = temp1.next
		temp1.next = head2
		head2 = head2.next
		temp1 = temp1.next
	temp1.next = head1
	temp2.next = head2
	return [final1.next, final2.next]


def mergeList(head1, head2):
	f_head1 = curr1 = node(None)
	f_head2 = curr2 = node(None)
	while head1 and head2:
		curr1.next = head1
		head1 = head1.next
		curr1 = curr1.next
		curr1.next = head2
		head2 = head2.next
		curr1 = curr1.next
	curr1.next = head1
	curr2.next = head2
	return [f_head1.next, f_head2.next]


def mergeList(head1, head2):
	curr1 = head1
	nxt1 = curr1.next
	curr2 = head2
	nxt2 = curr2.next
	while curr1 or curr2:
		if curr1 and curr2 and nxt1:
			curr1.next = curr2
			curr2.next = nxt1
			curr1 = nxt1
			curr2 = nxt2
			if nxt1:
				nxt1 = nxt1.next
			if nxt2:
				nxt2 = nxt2.next
				head2 = nxt2
		elif not curr2:
			head2 = None
			break
		elif curr1 and curr2:
			curr1.next = curr2
			head2 = curr2.next
			curr2.next = None
			break
	return [head1, head2]


def mergeList(head1, head2):
	temp = head1
	while head1 and head2:
		(t1, t2) = (head1.next, head2.next)
		head1.next = head2
		head2.next = t1
		(head1, head2) = (t1, t2)
	return [temp, head2]


def mergeList(head1, head2):
	node1 = head1
	node2 = head2
	f1 = temp1 = node(None)
	f2 = temp2 = node(None)
	while head1 and head2:
		temp1.next = head1
		head1 = head1.next
		temp1 = temp1.next
		temp1.next = head2
		head2 = head2.next
		temp1 = temp1.next
	temp1.next = head1
	temp2.next = head2
	return [f1.next, f2.next]


def mergeList(head1, head2):
	curr1 = head1
	curr2 = head2
	while curr1 != None and curr2 != None:
		onenext = curr1.next
		secondnext = curr2.next
		curr2.next = onenext
		curr1.next = curr2
		curr1 = onenext
		curr2 = secondnext
		head2 = curr2
	return [head1, head2]


def mergeList(head1, head2):
	current1 = head1
	current2 = head2
	while current1 and current2:
		next1 = current1.next
		next2 = current2.next
		current2.next = next1
		current1.next = current2
		current1 = next1
		current2 = next2
		head2 = current2
	return [head1, head2]


def mergeList(head1, head2):
	p_curr = head1
	q_curr = head2
	while p_curr and q_curr:
		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
		head2 = q_curr
	return [head1, head2]


def mergeList(head1, head2):
	l = []
	m = []
	while head1:
		l.append(head1.data)
		head1 = head1.next
	while head2:
		m.append(head2.data)
		head2 = head2.next
	ss = []
	mm = []
	if len(l) > len(m):
		for i in range(len(m)):
			ss.append(l[i])
			ss.append(m[i])
		mm = l[len(m):]
	else:
		for i in range(len(l)):
			ss.append(l[i])
			ss.append(m[i])
		mm = m[len(l):]
	mm = mm[::-1]
	ss = ss[::-1]
	pp = Linked_List()
	for i in ss:
		pp.insert(i)
	ppp = Linked_List()
	for i in mm:
		ppp.insert(i)
	s = pp.head
	if len(l) > len(m):
		while s.next:
			s = s.next
		s.next = ppp.head
		return [pp.head, None]
	return [pp.head, ppp.head]


def mergeList(head1, head2):
	l1 = head1
	l2 = head2
	a = []
	b = []
	main = []
	while l1:
		a.append(l1.data)
		l1 = l1.next
	while l2:
		b.append(l2.data)
		l2 = l2.next
	km = len(a)
	gm = len(b)
	if km > gm:
		for x in range(0, km):
			main.append(a[x])
			if x < gm:
				main.append(b[x])
	else:
		for x in range(0, gm):
			if x < km:
				main.append(a[x])
			main.append(b[x])
	xd = len(a) * 2
	ha1 = main[0:xd]
	ha2 = main[xd:len(main)]
	ha1.reverse()
	ha2.reverse()
	x = createList(ha1, len(ha1))
	y = createList(ha2, len(ha2))
	return [x, y]


def mergeList(head1, head2):
	h1 = head1
	h2 = head2
	while h1 != None and h2 != None:
		p = h1.next
		l = node(h2.data)
		l.next = p
		h1.next = l
		h1 = p
		h2 = h2.next
	return [head1, h2]


def mergeList(head1, head2):
	(t1, t2) = (head1, head2)
	while t1 and t2:
		temp = t1.next
		l = node(t2.data)
		l.next = temp
		t1.next = l
		t1 = temp
		t2 = t2.next
	return [head1, t2]


def mergeList(head1, head2):
	t1 = head1
	t2 = head2
	while t1 and t2:
		p1 = t1.next
		p2 = t2.next
		t1.next = t2
		t2.next = p1
		t1 = p1
		t2 = p2
	if t2:
		head2 = t2
	if t1 is None and t2 is None or t2 is None:
		return [head1, None]
	else:
		return [head1, head2]


def mergeList(head1, head2):
	temp = head1
	c1 = temp
	temp1 = head2
	while temp and temp1:
		cur = temp.next
		cu2 = temp1.next
		temp.next = temp1
		temp1.next = cur
		temp = cur
		temp1 = cu2
	head1 = c1
	head2 = temp1
	return [head1, head2]


def mergeList(head1, head2):
	res1 = []
	res2 = []
	while head1:
		res1.append(head1.data)
		head1 = head1.next
	n = 2 * len(res1)
	while head2:
		res2.append(head2.data)
		head2 = head2.next
	ans = []
	while res1 or res2:
		if res1:
			ans.append(res1[0])
			res1.pop(0)
		if res2:
			ans.append(res2[0])
			res2.pop(0)
	n = min(len(ans), n)
	x = ans[:n]
	x = x[::-1]
	x = createList(x, len(x))
	y = ans[n:]
	y = y[::-1]
	y = createList(y, len(y))
	return [x, y]

class node:

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

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, val):
		new_node = node(val)
		new_node.data = val
		new_node.next = self.head
		self.head = new_node

def printList(head):
	while head:
		print(head.data, end=' ')
		head = head.next
	print()

def createList(arr, n):
	lis = Linked_List()
	for i in range(n):
		lis.insert(arr[i])
	return lis.head
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		head1 = createList(arr, n)
		n = int(input())
		arr = list(map(int, input().strip().split()))
		head2 = createList(arr, n)
		head = mergeList(head1, head2)
		printList(head[0])
		printList(head[1])


def mergeList(head1, head2):
	curr1 = head1
	curr2 = head2
	while curr1 != None or curr2 != None:
		if curr1 != None and curr2 != None:
			temp1 = curr1.next
			temp2 = curr2.next
			curr1.next = curr2
			curr2.next = temp1
			curr1 = temp1
			curr2 = temp2
		elif curr1 != None:
			break
		else:
			break
	return [head1, curr2]

class node:

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

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, val):
		new_node = node(val)
		new_node.data = val
		new_node.next = self.head
		self.head = new_node

def printList(head):
	while head:
		print(head.data, end=' ')
		head = head.next
	print()

def createList(arr, n):
	lis = Linked_List()
	for i in range(n):
		lis.insert(arr[i])
	return lis.head
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		head1 = createList(arr, n)
		n = int(input())
		arr = list(map(int, input().strip().split()))
		head2 = createList(arr, n)
		head = mergeList(head1, head2)
		printList(head[0])
		printList(head[1])


def mergeList(head1, head2):
	lptr1 = head1
	lptr2 = head2
	while lptr1 != None and lptr2 != None:
		head2 = lptr2.next
		lptr2.next = lptr1.next
		lptr1.next = lptr2
		lptr1 = lptr2.next
		lptr2 = head2
	return [head1, head2]


def merge(a, b, alt):
	if a is None:
		return (None, b)
	if b is None:
		return (a, None)
	r = None
	if alt:
		r = node(b.data)
		(r.next, b) = merge(a.next, b.next, False)
	else:
		r = a
		(a.next, b) = merge(a, b, True)
	return (r, b)

def mergeList(head1, head2):
	return merge(head1, head2, False)


def mergeList(head1, head2):
	curr_head1 = head1
	curr_head2 = head2
	while curr_head1 and curr_head2:
		head1next = curr_head1.next
		head2next = curr_head2.next
		curr_head2.next = head1next
		curr_head1.next = curr_head2
		curr_head1 = head1next
		curr_head2 = head2next
		head2 = curr_head2
	return [head1, head2]


def mergeList(head1, head2):
	cur = head1
	while cur:
		after = cur.next
		if head2:
			temp = head2
			head2 = head2.next
			temp.next = after
			cur.next = temp
		cur = after
	return [head1, head2]


def mergeList(head1, head2):
	abc = curr1 = head1
	curr2 = head2
	while curr1 and curr2:
		temp1 = curr1.next
		temp2 = curr2.next
		curr1.next = curr2
		curr2.next = temp1
		curr1 = temp1
		curr2 = temp2
	return [head1, curr2]


def mergeList(head1, head2):
	n1 = head1
	n2 = head2
	f1 = t1 = node(None)
	f2 = t2 = node(None)
	while head1 and head2:
		t1.next = head1
		head1 = head1.next
		t1 = t1.next
		t1.next = head2
		head2 = head2.next
		t1 = t1.next
	t1.next = head1
	t2.next = head2
	return [f1.next, f2.next]


def mergeList(head1, head2):
	tmp1 = head1
	tmp2 = head2
	final1 = node1 = node(None)
	final2 = node2 = node(None)
	while tmp1 and tmp2:
		node1.next = tmp1
		tmp1 = tmp1.next
		node1 = node1.next
		node1.next = tmp2
		tmp2 = tmp2.next
		node1 = node1.next
	node1.next = tmp1
	node2.next = tmp2
	return [final1.next, final2.next]


def mergeList(head1, head2):
	h1 = head1
	h2 = head2
	while h1 and h2:
		n1 = h1.next
		n2 = h2.next
		h1.next = h2
		h2.next = n1
		h1 = n1
		h2 = n2
		head2 = h2
	return [head1, head2]


def mergeList(head1, head2):
	(c, n, prev) = (head1, head1.next, head1)
	ptr = head2
	while n != None and ptr != None:
		c = n
		n = n.next
		prev.next = ptr
		q = ptr.next
		ptr.next = c
		prev = c
		ptr = q
	if ptr != None:
		c.next = ptr
		q = ptr.next
		ptr.next = None
	head2 = q
	return [head1, head2]


def mergeList(head1, head2):
	(h1, h2) = (head1, head2)
	h1_prev = None
	while h1 and h2:
		temp1 = h1.next
		temp2 = h2.next
		h1.next = h2
		h1.next.next = temp1
		h2 = temp2
		h1_prev = h1.next
		h1 = h1.next.next
	return [head1, h2]


def mergeList(head1, head2):
	p1 = head1
	p2 = head2
	ind = 0
	while p1 and p2:
		if ind % 2 == 0:
			temp_p1 = p1.next
			p1.next = p2
			p1 = temp_p1
		else:
			temp_p2 = p2.next
			p2.next = p1
			p2 = temp_p2
		ind += 1
	if p2 and p2.next:
		head2 = p2.next
		p2.next = None
	else:
		head2 = None
	return [head1, head2]


def mergeList(head1, head2):
	dumpy = curr = node(None)
	dumpy2 = curr2 = node(None)
	while head1 and head2:
		curr.next = head1
		head1 = head1.next
		curr = curr.next
		curr.next = head2
		head2 = head2.next
		curr = curr.next
	curr.next = head1
	curr2.next = head2
	return [dumpy.next, dumpy2.next]


def mergeList(head1, head2):
	node1 = head1
	node2 = head2
	while node1 and node2:
		next1 = node1.next
		node1.next = node2
		node1 = next1
		next2 = node2.next
		node2.next = next1
		node2 = next2
	head2 = node2
	return [head1, head2]


def mergeList(head1, head2):
	p = head1
	q = head2
	while p and q:
		t1 = p.next
		t2 = q.next
		p.next = q
		q.next = t1
		if t2 is None:
			return [head1, None]
		if t1 is None:
			return [head1, t2]
		p = t1
		q = t2
	return [head1, head2]


def mergeList(head1, head2):
	temp1 = head1
	while temp1 and head2:
		newNode = node(head2.data)
		newNode.next = temp1.next
		temp1.next = newNode
		temp1 = temp1.next.next
		head2 = head2.next
	return [head1, head2]


def mergeList(head1, head2):
	p1 = head1
	while p1 and head2:
		new = node(head2.data)
		new.next = p1.next
		p1.next = new
		p1 = p1.next.next
		head2 = head2.next
	return [head1, head2]


def mergeList(head1, head2):
	cur_1 = head1
	cur_2 = head2
	while cur_1 and cur_2:
		tmp_1 = cur_1.next
		tmp_2 = cur_2.next
		cur_1.next = cur_2
		cur_2.next = tmp_1
		cur_1 = cur_1.next.next
		cur_2 = tmp_2
	return [head1, cur_2]


def mergeList(head1, head2):
	hea1 = head1
	hea2 = head2
	while hea1 != None and hea2 != None:
		p = hea1.next
		l = node(hea2.data)
		l.next = p
		hea1.next = l
		hea1 = p
		hea2 = hea2.next
	return [head1, hea2]


def mergeList(head1, head2):
	r1 = head1
	r2 = head2
	head = tail = None
	while r1 and r2:
		if head == None:
			head = node(r1.data)
			tail = head
			tail.next = node(r2.data)
			tail = tail.next
		else:
			tail.next = node(r1.data)
			tail = tail.next
			tail.next = node(r2.data)
			tail = tail.next
		r1 = r1.next
		r2 = r2.next
	head1 = tail1 = None
	while r1:
		if head == None:
			head = node(r1.data)
			tail = head
		else:
			tail.next = node(r1.data)
			tail = tail.next
		r1 = r1.next
	while r2:
		if head1 == None:
			head1 = node(r2.data)
			tail1 = head1
		else:
			tail1.next = node(r2.data)
			tail1 = tail1.next
		r2 = r2.next
	return [head, head1]


def mergeList(head1, head2):
	node1 = head1
	node2 = head2
	while node1 and node2:
		node1next = node1.next
		node1.next = node2
		node1 = node1next
		node2next = node2.next
		node2.next = node1next
		node2 = node2next
	head2 = node2
	return [head1, head2]


def mergeList(head1, head2):
	if head1 == None:
		return [None, head2]
	if head2 == None:
		return [head2, None]
	dummy = tail = node(100)
	temp1 = head1
	arr1 = []
	while temp1 != None:
		arr1.append(temp1.data)
		temp1 = temp1.next
	arr1[::-1]
	arr2 = []
	temp2 = head2
	while temp2 != None:
		arr2.append(temp2.data)
		temp2 = temp2.next
	arr2[::-1]
	curr = 0
	while curr < len(arr1) and curr < len(arr2):
		nw = node(arr1[curr])
		tail.next = nw
		tail = tail.next
		mw = node(arr2[curr])
		tail.next = mw
		tail = tail.next
		curr += 1
	dummy2 = tail2 = node(102)
	if curr < len(arr1):
		while curr < len(arr1):
			nw = node(arr1[curr])
			tail.next = nw
			tail = tail.next
			curr += 1
	elif curr < len(arr2):
		while curr < len(arr2):
			mw = node(arr2[curr])
			tail2.next = mw
			tail2 = tail2.next
			curr += 1
	return [dummy.next, dummy2.next]


def mergeList(head1, head2):
	list1_start = list2_start = list1_end = list2_end = None
	x = head1
	y = head2
	while x and y:
		if not list1_start:
			list1_start = x
			list1_end = list1_start
		else:
			list1_end.next = list2_end
			list1_end = x
		if not list2_start:
			list2_start = y
			list2_end = list2_start
		else:
			list2_end.next = x
			list2_end = y
		x = x.next
		y = y.next
	list1_end.next = list2_end
	head2 = list2_end.next
	list2_end.next = None
	if y:
		list1_end.next = list2_end
	if x:
		list1_end.next = list2_end
		list2_end.next = x
	return [head1, head2]


def mergeList(head1, head2):
	f_curr = head1
	s_curr = head2
	while f_curr is not None and s_curr is not None:
		f_next = f_curr.next
		s_next = s_curr.next
		s_curr.next = f_next
		f_curr.next = s_curr
		f_curr = f_next
		s_curr = s_next
		head2 = s_curr
	return [head1, head2]


def mergeList(head1, head2):
	result = head1
	if not result:
		return head2
	at_alternate = True
	while head1 and head2:
		temp = head2.next
		head2.next = head1.next
		head1.next = head2
		(head1, head2) = (head1.next.next, temp)
	return [result, head2]


def mergeList(head1, head2):
	a = head1
	b = head2
	while a:
		temp = a.next
		if not b:
			break
		a.next = b
		prev = b
		b = b.next
		prev.next = temp
		a = temp
	head2 = b
	return [head1, head2]


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

def mergeList(head1, head2):
	p_curr = head1
	q_curr = head2
	while p_curr != None and q_curr != None:
		p_next = p_curr.next
		q_next = q_curr.next
		p_curr.next = q_curr
		q_curr.next = p_next
		p_curr = p_next
		q_curr = q_next
	return [head1, q_curr]


def mergeList(head1, head2):
	if head1 and (not head2):
		return [head1, head2]
	elif head2 and (not head1):
		return [head2, head1]
	curr1 = head1
	curr2 = head2
	while curr1:
		if curr2:
			temp1 = curr1.next
			curr1.next = curr2
			temp2 = curr2.next
			curr2.next = temp1
			curr1 = temp1
			curr2 = temp2
			head2 = curr2
		else:
			break
	return [head1, head2]


def mergeList(head1, head2):
	n = head1
	m = head2
	temp1 = head1
	temp2 = head2
	head3 = n
	while temp1 != None:
		temp1 = temp1.next
		n.next = temp2
		n = n.next
		temp2 = temp2.next
		n.next = temp1
		n = n.next
		if temp1 == None or temp2 == None:
			break
	if temp2 != None:
		m = temp2
		head4 = m
	else:
		head4 = None
	return (head3, head4)


def mergeList(h1, h2):
	(p, q) = (h1, h2)
	while p and q:
		(p_nxt, q_nxt) = (p.next, q.next)
		(q.next, p.next) = (p_nxt, q)
		(p, q) = (p_nxt, q_nxt)
		h2 = q
	return (h1, h2)


def mergeList(head1, head2):
	if head1 == None or head2 == None:
		return [head1, head2]
	current1 = head1
	current2 = head2
	while current1 != None and current2 != None:
		next1 = current1.next
		next2 = current2.next
		current1.next = current2
		current2.next = next1
		current1 = next1
		current2 = next2
	head2 = current2
	return [head1, head2]


def mergeList(head1, head2):
	(p1, p2) = (head1, head2)
	while p1 and p2:
		nextt = p1.next
		temp = node(p2.data)
		p1.next = temp
		temp.next = nextt
		p1 = p1.next.next
		p2 = p2.next
	return [head1, p2]


def mergeList(head1, head2):
	if head2 == None or head1 == None:
		return [head1, head2]
	new1 = node(0)
	n1d = new1
	new2 = node(0)
	n2d = new2
	while head1 and head2:
		n1d.next = node(head1.data)
		n1d = n1d.next
		n1d.next = node(head2.data)
		n1d = n1d.next
		head1 = head1.next
		head2 = head2.next
	if head2:
		n2d.next = node(head2).data
		n2d = n2d.next
		head2 = head2.next
	if head1:
		n1d.next = node(head1).data
		n1d = n1d.next
		head1 = head1.next
	return [new1.next, new2.next]


def mergeList(head1, head2):
	ptr1 = head1
	ptr2 = head2
	while ptr1 and ptr2:
		next1 = ptr1.next
		next2 = ptr2.next
		ptr2.next = next1
		ptr1.next = ptr2
		ptr1 = next1
		ptr2 = next2
		head2 = ptr2
	return [head1, head2]


def mergeList(head1, head2):
	flag = 0
	if head1 == None:
		return head2
	if head2 == None:
		return head1
	flag = 0
	p_curr = head1
	q_curr = head2
	while p_curr != None and q_curr != 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
		head2 = q_curr
	return [head1, head2]


def mergeList(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	hea1 = head1
	hea2 = head2
	last = head1
	while hea1 is not None and hea2 is not None:
		temp1 = hea1.next
		hea1.next = hea2
		last = temp2 = hea2
		hea2 = hea2.next
		temp2.next = temp1
		hea1 = temp1
	return [head1, hea2]


def mergeList(head1, head2):
	if head1 == None:
		return [head1, head2]
	if head2 == None:
		return [head1, head2]
	temp1 = head1
	temp2 = head2
	while temp1 != None:
		tempi = temp1.next
		temp1.next = temp2
		temp2 = temp2.next
		temp1.next.next = tempi
		temp1 = temp1.next.next
		if temp2 == None:
			break
	return [head1, temp2]


def mergeList(head1, head2):
	c1 = head1
	c2 = head2
	while c1 != None or c2 != None:
		if c1 != None and c2 != None:
			t1 = c1.next
			t2 = c2.next
			c1.next = c2
			c2.next = t1
			c1 = t1
			c2 = t2
		elif c1 != None:
			break
		else:
			break
	return [head1, c2]