Given a singly linked list, the task is to rearrange it in a way that all odd position nodes are together and all even positions node are together.
Assume the first element to be at position 1 followed by second element at position 2 and so on.
Note: You should place all odd positioned nodes first and then the even positioned ones. (considering 1 based indexing). Also, the relative order of odd positioned nodes and even positioned nodes should be maintained.
Example 1:
Input:
LinkedList: 1->2->3->4
Output: 1 3 2 4 
Explanation: 
Odd elements are 1, 3 and even elements are 
2, 4. Hence, resultant linked list is 
1->3->2->4.
Example 2:
Input:
LinkedList: 1->2->3->4->5
Output: 1 3 5 2 4 
Explanation: 
Odd elements are 1, 3, 5 and even elements are
2, 4. Hence, resultant linked list is
1->3->5->2->4.
Your Task:
The task is to complete the function rearrangeEvenOdd() which rearranges the nodes in the linked list as required and doesn't return anything.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ Size of the linked list ≤ 10^{4}
0 ≤ value of linked list ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



'''

# Linked List Node 

class Node: 

	def __init__(self, d): 

		self.data = d 

		self.next = None

		'''

class Solution:    

    def rearrangeEvenOdd(self, head):

        #code here

Solutions:
class Solution:

	def rearrangeEvenOdd(self, head):
		i = 0
		even = []
		odd = []
		a = []
		temp1 = head
		temp2 = head
		while temp1:
			i += 1
			if i % 2 == 0:
				even.append(temp1.data)
			else:
				odd.append(temp1.data)
			temp1 = temp1.next
		a = odd + even
		for item in a:
			temp2.data = item
			temp2 = temp2.next
		return head


class Solution:

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


class Solution:

	def rearrangeEvenOdd(self, head):
		if head.next == None:
			return None
		head1 = odd = head
		head2 = even = head.next
		while odd and even:
			odd.next = even.next
			prev = odd
			odd = odd.next
			if odd != None:
				even.next = odd.next
				even = even.next
		if odd != None:
			odd.next = head2
		else:
			prev.next = head2
		return head1


class Solution:

	def rearrangeEvenOdd(self, head):
		e = None
		o = None
		temp = head
		i = 1
		while temp != None:
			node = temp
			temp = temp.next
			node.next = None
			if i == 1:
				if o == None:
					o = node
					otemp = o
				else:
					otemp.next = node
					otemp = otemp.next
				i = 0
			else:
				if e == None:
					e = node
					etemp = e
				else:
					etemp.next = node
					etemp = etemp.next
				i = 1
		otemp.next = e
		return o


class Solution:

	def rearrangeEvenOdd(self, head):
		if head is None or head.next is None:
			return
		(os, es, oe, ee) = (None, None, None, None)
		c = head
		res = 1
		while c is not None:
			if res % 2 != 0:
				if os is None:
					os = oe = c
				else:
					oe.next = c
					oe = oe.next
			elif res % 2 == 0:
				if es is None:
					es = ee = c
				else:
					ee.next = c
					ee = ee.next
			c = c.next
			res += 1
		oe.next = es
		if es is not None:
			ee.next = None
		head = es


class Solution:

	def rearrangeEvenOdd(self, head):
		h = head
		evenPos = []
		oddPos = []
		llarr = []
		while h:
			llarr.append(h.data)
			h = h.next
		for i in range(len(llarr)):
			if i % 2 == 0:
				evenPos.append(llarr[i])
			else:
				oddPos.append(llarr[i])
		resarr = evenPos + oddPos
		h = head
		i = 0
		while h:
			h.data = resarr[i]
			i += 1
			h = h.next


class Solution:

	def rearrangeEvenOdd(self, head):
		(odd, odd_start) = (head, head)
		(even, even_start) = (head.next, head.next)
		while odd and even:
			odd.next = even.next
			prev = odd
			odd = odd.next
			if odd:
				even.next = odd.next
				even = even.next
		if not odd:
			prev.next = even_start
		else:
			odd.next = even_start
		return odd_start


class Solution:

	def rearrangeEvenOdd(self, head):
		even = []
		odd = []
		n = head
		i = 1
		while n is not None:
			if i % 2 != 0:
				odd.append(n.data)
			else:
				even.append(n.data)
			i = i + 1
			n = n.next
		L = odd + even
		n = head
		while n is not None:
			n.data = L.pop(0)
			n = n.next


class Solution:

	def rearrangeEvenOdd(self, head):
		evenhead = Node(0)
		oddhead = Node(0)
		t_even = evenhead
		t_odd = oddhead
		i = 1
		while head is not None:
			if i % 2 == 0:
				t_even.next = head
				head = head.next
				t_even = t_even.next
				t_even.next = None
			else:
				t_odd.next = head
				head = head.next
				t_odd = t_odd.next
				t_odd.next = None
			i += 1
		if evenhead.next is None:
			del evenhead
			return oddhead.next
		if oddhead.next is None:
			del oddhead
			return evenhead.next
		head = oddhead.next
		t_odd.next = evenhead.next
		del evenhead
		del oddhead


class Solution:

	def rearrangeEvenOdd(self, head):
		odd = head
		even = even_head = head.next
		while even and even.next:
			odd.next = odd.next.next
			odd = odd.next
			even.next = even.next.next
			even = even.next
		odd.next = even_head
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		ehead = None
		tehead = None
		ohead = None
		tohead = None
		count = 1
		while head:
			ans = head
			head = head.next
			ans.next = None
			if count & 1 == 1:
				if tohead == None:
					tohead = ans
					ohead = tohead
				else:
					tohead.next = ans
					tohead = tohead.next
			elif tehead == None:
				tehead = ans
				ehead = tehead
			else:
				tehead.next = ans
				tehead = tehead.next
			count += 1
		tohead.next = ehead
		return ohead


class Solution:

	def rearrangeEvenOdd(self, head):
		even = odd = None
		et = ot = None
		i = 0
		while head:
			if i % 2 == 0:
				if not even:
					even = head
					et = head
				else:
					even.next = head
					even = even.next
			elif not odd:
				odd = head
				ot = head
			else:
				odd.next = head
				odd = odd.next
			i += 1
			head = head.next
		if odd:
			odd.next = None
		even.next = ot
		return et


class Solution:

	def rearrangeEvenOdd(self, head):
		odd = None
		even = None
		newodd = None
		neweven = None
		flag = True
		while head:
			next = head.next
			if flag:
				if odd == None:
					odd = head
					newodd = head
				else:
					odd.next = head
					odd = head
			elif even == None:
				even = head
				neweven = head
			else:
				even.next = head
				even = head
			flag = not flag
			head = next
		if even:
			even.next = None
		odd.next = neweven
		return newodd


import math

class Solution:

	def rearrangeEvenOdd(self, head):
		if not head:
			return None
		(even, odd) = (Node(-1), Node(-1))
		(evenHead, oddHead) = (even, odd)
		temp = head
		while temp:
			odd.next = temp
			odd = odd.next
			temp = temp.next
			even.next = temp
			even = even.next
			if temp:
				temp = temp.next
		head = oddHead.next
		odd.next = evenHead.next


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None or head.next == None:
			return head
		oddnod = head
		evennod = head.next
		curnod = evennod.next
		evenhead = evennod
		pos = 1
		while curnod != None:
			if pos & 1:
				oddnod.next = curnod
				oddnod = curnod
			else:
				evennod.next = curnod
				evennod = curnod
			pos += 1
			curnod = curnod.next
		oddnod.next = evenhead
		evennod.next = None
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		s = head
		odd = []
		eve = []
		i = 1
		while s:
			if i % 2:
				odd.append(s.data)
			else:
				eve.append(s.data)
			s = s.next
			i += 1
		s = head
		while odd:
			s.data = odd.pop(0)
			s = s.next
		while eve:
			s.data = eve.pop(0)
			s = s.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		odd = head
		even = head.next
		even_start = head.next
		if odd is None:
			return None
		while even and even.next:
			odd.next = even.next
			even.next = even.next.next
			odd = odd.next
			even = even.next
		odd.next = even_start
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		odd = Node(-1)
		t1 = odd
		even = Node(-1)
		t2 = even
		cur = head
		i = 1
		while cur != None:
			if i % 2 == 1:
				t1.next = cur
				t1 = t1.next
			else:
				t2.next = cur
				t2 = t2.next
			i += 1
			cur = cur.next
		t2.next = None
		t1.next = even.next
		head = odd.next


class Solution:

	def rearrangeEvenOdd(self, head):
		even = []
		odd = []
		res = []
		i = 1
		temp1 = head
		temp2 = head
		while temp1:
			if i % 2 == 0:
				even.append(temp1.data)
			else:
				odd.append(temp1.data)
			temp1 = temp1.next
			i += 1
		res = odd + even
		for i in res:
			temp2.data = i
			temp2 = temp2.next


class Solution:

	def rearrangeEvenOdd(self, head):
		o = head
		p = head.next
		e = head.next
		while (o.next != None and e != None) and (o.next.next != None and e.next != None):
			o.next = o.next.next
			e.next = e.next.next
			o = o.next
			e = e.next
		o.next = p


class Solution:

	def rearrangeEvenOdd(self, head):
		e = []
		o = []
		l = []
		cur = head
		temp = head
		i = 1
		while cur:
			if i % 2 != 0:
				o.append(cur.data)
				cur = cur.next
			else:
				e.append(cur.data)
				cur = cur.next
			i += 1
		l = o + e
		for i in l:
			temp.data = i
			temp = temp.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		temp = head
		c = 1
		while temp.next:
			c += 1
			temp = temp.next
		temp1 = head
		temp2 = head.next
		a = 2
		while a <= c:
			temp.next = temp2
			temp1.next = temp2.next
			temp2 = temp2.next.next
			temp1 = temp1.next
			temp = temp.next
			a += 2
		temp.next = None


class Solution:

	def rearrangeEvenOdd(self, head):
		c = 0
		e = []
		o = []
		l = []
		temp1 = head
		temp2 = head
		while temp1:
			c += 1
			if c % 2 == 0:
				e.append(temp1.data)
			else:
				o.append(temp1.data)
			temp1 = temp1.next
		l = o + e
		for i in l:
			temp2.data = i
			temp2 = temp2.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		ev = []
		od = []
		cur = head
		itr = head
		i = 1
		while cur:
			if i % 2 == 0:
				ev.append(cur.data)
			else:
				od.append(cur.data)
			i += 1
			cur = cur.next
		k = od + ev
		for i in range(len(k)):
			head.data = k[i]
			head = head.next


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None or head.next == None:
			return head
		oddNode = head
		evenNode = head.next
		currNode = evenNode.next
		evenhead = evenNode
		pos = 1
		while currNode != None:
			if pos & 1:
				oddNode.next = currNode
				oddNode = currNode
			else:
				evenNode.next = currNode
				evenNode = currNode
			pos = pos + 1
			currNode = currNode.next
		oddNode.next = evenhead
		evenNode.next = None


class Solution:

	def rearrangeEvenOdd(self, head):
		count = 0
		ptr = head
		(e, o) = (Node(-1), Node(-1))
		(ep, op) = (e, o)
		while ptr:
			count += 1
			if count % 2 == 1:
				op.next = ptr
				op = op.next
				ptr = ptr.next
			else:
				ep.next = ptr
				ep = ep.next
				ptr = ptr.next
		ep.next = None
		op.next = None
		ptr = o
		while ptr.next:
			ptr = ptr.next
		ptr.next = e.next


class Solution:

	def rearrangeEvenOdd(self, head):
		if head.next == None:
			return
		count = 0
		ohead = None
		odd = None
		ehead = None
		even = None
		current = head
		while current != None:
			if count % 2 == 0:
				if ohead == None:
					ohead = current
					odd = current
				else:
					odd.next = current
					odd = current
			elif ehead == None:
				ehead = current
				even = current
			else:
				even.next = current
				even = current
			count += 1
			current = current.next
		even.next = None
		odd.next = ehead


class Solution:

	def rearrangeEvenOdd(self, head):
		if not head.next:
			return head
		tail = head
		while tail.next:
			tail = tail.next
		tail.next = Node('-1')
		tail = tail.next
		start = tail
		cur = head
		prev = None
		pos = 0
		while cur:
			if cur == start:
				break
			elif pos & 1 != 1:
				prev = cur
				cur = cur.next
			elif prev is None:
				head = cur.next
				cur.next = None
				tail.next = cur
				tail = tail.next
				cur = head
			else:
				temp = cur.next
				prev.next = temp
				cur.next = None
				tail.next = cur
				tail = tail.next
				cur = temp
			pos += 1
		cur = head
		prev = None
		while cur:
			if cur == start:
				break
			prev = cur
			cur = cur.next
		prev.next = cur.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		num = []
		t = head
		while t:
			num.append(t.data)
			t = t.next
		num1 = num[0:len(num):2]
		num2 = num[1:len(num):2]
		n3 = num1 + num2
		temp = head
		i = 0
		while temp != None:
			temp.data = n3[i]
			i += 1
			temp = temp.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		ind = 1
		odd = []
		even = []
		cur = head
		while cur:
			if ind & 1:
				odd.append(cur.data)
			else:
				even.append(cur.data)
			ind += 1
			cur = cur.next
		ans = odd + even
		ind1 = 0
		cur1 = head
		while cur1:
			cur1.data = ans[ind1]
			ind1 += 1
			cur1 = cur1.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None:
			return None
		odd = head
		even = head.next
		evenfirst = even
		while 1 == 1:
			if odd == None or even == None or even.next == None:
				odd.next = evenfirst
				break
			odd.next = even.next
			odd = even.next
			if odd.next == None:
				even.next = None
				odd.next = evenfirst
				break
			even.next = odd.next
			even = even.next


class Solution:

	def rearrangeEvenOdd(self, head):
		odd = head
		even = head.next
		evenfirst = even
		while odd.next and even.next:
			if odd.next:
				odd.next = odd.next.next
				odd = odd.next
			if even.next:
				even.next = even.next.next
				even = even.next
		odd.next = evenfirst
		return odd


class Solution:

	def rearrangeEvenOdd(self, head):
		v1 = []
		v2 = []
		temp = head
		i = 0
		while temp:
			i += 1
			if i % 2 != 0:
				v1.append(temp.data)
			else:
				v2.append(temp.data)
			temp = temp.next
		temp = head
		for i in range(len(v1)):
			temp.data = v1[i]
			temp = temp.next
		for i in range(len(v2)):
			temp.data = v2[i]
			temp = temp.next


class Solution:

	def rearrangeEvenOdd(self, head):
		dummy = Node(0)
		curr = dummy
		temp = head
		odd = temp
		while temp.next:
			ptr = temp.next
			temp.next = ptr.next
			ptr.next = None
			curr.next = ptr
			curr = ptr
			if temp.next:
				temp = temp.next
		temp.next = dummy.next
		return odd


class Solution:

	def rearrangeEvenOdd(self, head):
		if not head:
			return head
		odd = Node(-1)
		even = Node(-1)
		od = odd
		ev = even
		temp = head
		flag = True
		while temp:
			if flag:
				odd.next = temp
				odd = odd.next
			else:
				even.next = temp
				even = even.next
			flag = not flag
			temp = temp.next
		even.next = None
		odd.next = ev.next
		head = od.next


class Solution:

	def rearrangeEvenOdd(self, head):
		i = 1
		(arr1, arr2) = ([], [])
		temp = head
		while temp:
			if i % 2 != 0:
				arr1.append(temp.data)
				i += 1
			else:
				arr2.append(temp.data)
				i += 1
			temp = temp.next
		temp = head
		(i, j) = (0, 0)
		while temp:
			if i < len(arr1):
				temp.data = arr1[i]
				i += 1
			else:
				temp.data = arr2[j]
				j += 1
			temp = temp.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		if not head:
			return None
		root1 = first = head
		root2 = second = head.next
		while first and second:
			if second.next:
				first.next = second.next
				first = first.next
				second.next = first.next
				second = second.next
			else:
				first.next = None
				second.next = None
				break
		first.next = root2
		return root1


class Solution:

	def rearrangeEvenOdd(self, head):
		dummy = even = head
		node = odd = head.next
		while even.next and odd.next:
			even.next = odd.next
			even = even.next
			odd.next = even.next
			odd = odd.next
		even.next = node
		return dummy


class Solution:

	def rearrangeEvenOdd(self, head):
		if head.next is None:
			return
		odd_head = head
		even_head = head.next
		even_first = even_head
		while True:
			if odd_head is None or even_head is None or even_head.next is None:
				odd_head.next = even_first
				break
			odd_head.next = even_head.next
			odd_head = odd_head.next
			if odd_head.next is None:
				odd_head.next = even_first
				even_head.next = None
				break
			even_head.next = odd_head.next
			even_head = even_head.next
		even_head.next = None


class Solution:

	def rearrangeEvenOdd(self, head):
		odd_head = Node(-1)
		odd_tail = odd_head
		even_head = Node(-1)
		even_tail = even_head
		curr = head
		i = 1
		while curr:
			if i % 2 == 0:
				even_tail.next = curr
				even_tail = even_tail.next
			else:
				odd_tail.next = curr
				odd_tail = odd_tail.next
			curr = curr.next
			i += 1
		even_tail.next = None
		odd_tail.next = even_head.next
		return odd_head.next


class Solution:

	def rearrangeEvenOdd(self, head):
		l1 = []
		l2 = []
		node = head
		i = 0
		while node != None:
			if i % 2 == 0:
				l1.append(node.data)
			else:
				l2.append(node.data)
			i += 1
			node = node.next
		node1 = head
		l = l1 + l2
		for i in l:
			node1.data = i
			node1 = node1.next


class Solution:

	def rearrangeEvenOdd(self, head):
		odd = head
		even = head.next
		evenHead = head.next
		while odd.next != None and even.next != None:
			odd.next = even.next
			odd = odd.next
			even.next = odd.next
			even = even.next
		odd.next = evenHead


class Solution:

	def rearrangeEvenOdd(self, head):
		(odd, even) = (list(), list())
		count = 0
		temp = temp2 = head
		while temp:
			count += 1
			if count % 2 == 0:
				even.append(temp.data)
			else:
				odd.append(temp.data)
			temp = temp.next
		ans = odd + even
		for i in ans:
			temp2.data = i
			temp2 = temp2.next


class Solution:

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


class Solution:

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


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None or head.next == None:
			return head
		odd = Node(-1)
		result = odd
		even = Node(-1)
		dummy = even
		i = 1
		while head:
			if i % 2 != 0:
				odd.next = head
				head = head.next
				odd = odd.next
			else:
				even.next = head
				head = head.next
				even = even.next
			i += 1
		odd.next = dummy.next
		even.next = None
		return result.next


class Solution:

	def rearrangeEvenOdd(self, head):
		a = []
		b = []
		c = []
		tmp = head
		while tmp != None:
			a.append(tmp.data)
			tmp = tmp.next
		for i in range(len(a)):
			if i % 2 == 0 or i == 0:
				b.append(a[i])
			else:
				c.append(a[i])
		tmp = head
		if len(b) != 0:
			for i in b:
				tmp.data = i
				tmp = tmp.next
		for i in c:
			tmp.data = i
			tmp = tmp.next
		return head


class Solution:

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


class Solution:

	def rearrangeEvenOdd(self, head):
		od = []
		ev = []
		temp = head
		i = 1
		while head:
			if i & 1 & 1:
				od += [head.data]
			else:
				ev += [head.data]
			i += 1
			head = head.next
		head = temp
		for i in od + ev:
			head.data = i
			head = head.next
		return temp


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None or head.next == None:
			return head
		ev = head
		odhead = head.next
		od = head.next
		while ev.next != None and od.next != None:
			ev.next = ev.next.next
			od.next = od.next.next
			ev = ev.next
			od = od.next
		ev.next = odhead


class Solution:

	def rearrangeEvenOdd(self, head):
		odd = []
		even = []
		count = 0
		current = head
		while current:
			count += 1
			if count % 2 == 0:
				even.append(current.data)
			else:
				odd.append(current.data)
			current = current.next
		odd = odd + even
		temp = head
		i = 0
		while temp:
			temp.data = odd[i]
			i += 1
			temp = temp.next


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None:
			return
		if head.next == None:
			return head
		itr = head
		even = Node(-1)
		odd = Node(-1)
		dummy = even
		curr = odd
		count = 1
		while itr:
			if count % 2 != 0:
				odd.next = itr
				itr = itr.next
				odd = odd.next
				odd.next = None
			else:
				even.next = itr
				itr = itr.next
				even = even.next
				even.next = None
			count += 1
		odd.next = dummy.next
		return curr.next


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None:
			return None
		oddtail = head
		evenhead = head.next
		eventail = head.next
		while eventail and eventail.next:
			oddtail.next = oddtail.next.next
			eventail.next = eventail.next.next
			oddtail = oddtail.next
			eventail = eventail.next
		oddtail.next = evenhead


class Solution:

	def rearrangeEvenOdd(self, head):
		c = head
		arr = []
		while c != None:
			arr.append(c.data)
			temp = c
			c = c.next
			temp.next = None
		(t1, t2) = (list(), list())
		i = 1
		while arr:
			if i & 1:
				t1.append(arr[0])
				del arr[0]
			else:
				t2.append(arr[0])
				del arr[0]
			i += 1
		print(*t1, *t2, end='')
		head.data = ''
		head.next = None


class Solution:

	def rearrangeEvenOdd(self, head):
		start = head
		start_even = head.next
		while head.next and head.next.next:
			temp = head.next
			head.next = head.next.next
			head = head.next
			temp.next = temp.next.next
			temp = temp.next
		head.next = start_even
		return start


class Solution:

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


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None:
			return
		even = head.next
		odd = head
		cur = head
		evenfi = even
		while odd != None and odd.next != None and (even != None) and (even.next != None):
			if odd.next:
				odd.next = even.next
				odd = odd.next
			if even.next:
				even.next = odd.next
				even = even.next
			odd.next = evenfi
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		temp = head
		if head == None or head.next == None:
			return
		curr = temp
		prev = None
		x = 1
		while temp != None:
			if x == 1 or x == 2:
				x += 1
				prev = temp
				temp = temp.next
				continue
			if x % 2 == 1:
				n = curr.next
				curr.next = temp
				o = temp.next
				temp.next = n
				curr = temp
				prev.next = o
				prev = o
			if o != None:
				temp = o.next
			else:
				temp = None
			x += 2


class Solution:

	def rearrangeEvenOdd(self, head):
		if head.next != None:
			odd = Node(0)
			even = Node(0)
			evenpointer = even
			oddpointer = odd
			current = head
			i = 1
			while current:
				if i % 2 == 1:
					oddpointer.next = current
					oddpointer = current
				else:
					evenpointer.next = current
					evenpointer = current
				current = current.next
				i += 1
			head = odd.next if odd.next else even.next
			oddpointer.next = even.next
			evenpointer.next = None
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		e = []
		o = []
		a = head
		b = head
		i = 0
		while a:
			i += 1
			if i % 2 == 0:
				e.append(a.data)
			else:
				o.append(a.data)
			a = a.next
		odd = o + e
		for i in odd:
			b.data = i
			b = b.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		temp = head
		temp1 = head.next
		head1 = head.next
		while temp.next and temp1.next:
			temp.next = temp1.next
			temp = temp.next
			temp1.next = temp.next
			temp1 = temp1.next
		if temp1 and temp1.next:
			temp = temp1.next
		temp.next = head1
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		even = []
		odd = []
		curr = head
		itr = head
		i = 1
		while curr:
			if i % 2 == 0:
				even.append(curr.data)
			else:
				odd.append(curr.data)
			i += 1
			curr = curr.next
		odd = odd + even
		dummy = Node(-1)
		temp = dummy
		for i in range(len(odd)):
			itr.data = odd[i]
			itr = itr.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		(odd, even) = self.split(head)
		cur = odd
		while cur.next:
			cur = cur.next
		cur.next = even
		return odd

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


class Solution:

	def rearrangeEvenOdd(self, head):
		(curr, oddNode, evenNode, counter) = (None, head, None, 3)
		if head.next:
			(curr, evenNode) = (head.next, head.next)
		if curr and curr.next:
			while curr.next:
				if counter % 2 == 0:
					curr = curr.next
					counter += 1
				else:
					t = curr.next
					if curr.next.next:
						curr.next = curr.next.next
					else:
						curr.next = None
					t.next = evenNode
					oddNode.next = t
					oddNode = oddNode.next
					counter += 1


class Solution:

	def rearrangeEvenOdd(self, head):
		if head:
			even_head = head.next
		odd_curr = head
		even_curr = odd_curr.next if odd_curr else None
		o_next = even_curr.next if even_curr else None
		e_next = o_next.next if o_next else None
		o_prev = odd_curr
		while odd_curr:
			odd_curr.next = o_next
			if even_curr:
				even_curr.next = e_next
			o_prev = odd_curr
			odd_curr = o_next
			even_curr = e_next
			o_next = o_next.next.next if o_next and o_next.next else None
			e_next = e_next.next.next if e_next and e_next.next else None
		o_prev.next = even_head
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None:
			return None
		odd = head
		even = head.next
		firstEven = even
		while True:
			if odd == None or even == None or even.next == None:
				odd.next = firstEven
				break
			odd.next = even.next
			odd = even.next
			if odd.next == None:
				even.next = None
				odd.next = firstEven
				break
			even.next = odd.next
			even = odd.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		od = []
		ev = []
		cur = head
		c = 0
		while cur != None:
			if c % 2 == 0:
				ev.append(cur.data)
			else:
				od.append(cur.data)
			c += 1
			cur = cur.next
		odev = ev + od
		curr = head
		for i in odev:
			curr.data = i
			curr = curr.next
		return head


class Solution:

	def rearrangeEvenOdd(self, head):
		if head == None:
			return head
		temp = head
		x = head
		y = head.next
		t = head
		while temp.next != None:
			ptemp = temp
			temp = temp.next
			ptemp.next = temp.next
		while x.next != None:
			x = x.next
		x.next = y
		return t