Given a link list of size N, modify the list such that all the even numbers appear before all the odd numbers in the modified list. The order of appearance of numbers within each segregation should be same as that in the original list.
NOTE: Don't create a new linked list, instead rearrange the provided one.
Example 1:
Input: 
N = 7
Link List:
17 -> 15 -> 8 -> 9 -> 2 -> 4 -> 6 -> NULL
Output: 8 2 4 6 17 15 9
Explaination: 8,2,4,6 are the even numbers 
so they appear first and 17,15,9 are odd 
numbers that appear later.
Example 2:
Input:
N = 4
Link List:
1 -> 3 -> 5 -> 7
Output: 1 3 5 7
Explaination: There is no even number. 
So ne need for modification.
Your Task:
You do not need to read input or print anything. Your task is to complete the function divide() which takes N and head of Link List as input parameters and returns the head of modified link list. Don't create a new linked list, instead rearrange the provided one.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Each element of the list ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: # User function Template for Python3

# Following is the structure of node 
# class Node:
#     def __init__(self):  
#         self.data = None
#         self.next = None

class Solution:
    def divide(self, N, head):
        # code here

Solutions:
class Solution:

	def divide(self, N, head):
		odd = None
		even = None
		o = None
		e = None
		curr = head
		while curr != None:
			if curr.data % 2 != 0:
				if odd == None:
					odd = curr
					o = curr
				else:
					o.next = curr
					o = o.next
			elif even == None:
				even = curr
				e = curr
			else:
				e.next = curr
				e = e.next
			curr = curr.next
		if odd == None:
			return even
		if even == None:
			return odd
		else:
			e.next = odd
			o.next = None
			return even


class Solution:

	def divide(self, N, head):
		os = None
		oe = None
		es = None
		ee = None
		curr = head
		while curr != None:
			if curr.data % 2 == 0:
				if es == None:
					es = curr
					ee = curr
				else:
					ee.next = curr
					ee = ee.next
			elif os == None:
				os = curr
				oe = curr
			else:
				oe.next = curr
				oe = oe.next
			curr = curr.next
		if os == None:
			return es
		if es == None:
			return os
		else:
			ee.next = os
			oe.next = None
			return es


class Solution:

	def divide(self, N, head):
		even_head = None
		odd_head = None
		even = None
		odd = None
		front = head
		while front is not None:
			if front.data % 2:
				if odd_head is None:
					odd_head = front
					odd = front
				else:
					odd.next = front
					odd = odd.next
				front = front.next
			else:
				if even_head is None:
					even_head = front
					even = front
				else:
					even.next = front
					even = even.next
				front = front.next
		if odd is not None:
			odd.next = None
		if even is not None:
			even.next = odd_head
			return even_head
		return odd_head


class Solution:

	def divide(self, N, head):
		temp = head
		even = node()
		odd = node()
		curr1 = odd
		curr = even
		while temp != None:
			if temp.data % 2 == 0:
				even.next = temp
				temp = temp.next
				even = even.next
				even.next = None
			else:
				odd.next = temp
				temp = temp.next
				odd = odd.next
				odd.next = None
		even.next = curr1.next
		return curr.next


class Solution:

	def divide(self, N, head):
		even = []
		odd = []
		itr = head
		while itr:
			if itr.data % 2 != 0:
				odd.append(itr.data)
			else:
				even.append(itr.data)
			itr = itr.next
		dummy = head
		if even:
			dummy.data = even.pop(0)
		else:
			dummy.data = odd.pop(0)
		while even or odd:
			dummy = dummy.next
			if even:
				dummy.data = even.pop(0)
			else:
				dummy.data = odd.pop(0)
		return head


class Solution:

	def divide(self, N, head):
		n = head
		(odd, heado) = (None, None)
		(even, heade) = (None, None)
		while n != None:
			if n.data % 2 != 0:
				if heado == None:
					odd = n
					heado = n
				else:
					odd.next = n
					odd = odd.next
			elif heade == None:
				even = n
				heade = n
			else:
				even.next = n
				even = even.next
			n = n.next
		if heado == None and heade != None:
			even.next = None
			return heade
		elif heade == None and heado != None:
			odd.next = None
			return heado
		elif heado != None and heade != None:
			even.next = heado
			odd.next = None
		return heade


class Solution:

	def divide(self, N, head):
		if head is None or head.next is None:
			return head
		even_head = None
		odd_head = None
		even_tail = None
		odd_tail = None
		cur = head
		while cur:
			if cur.data % 2 == 0:
				if even_head is None:
					even_head = cur
					even_tail = cur
				else:
					even_tail.next = cur
					even_tail = even_tail.next
			elif odd_head is None:
				odd_head = cur
				odd_tail = cur
			else:
				odd_tail.next = cur
				odd_tail = odd_tail.next
			cur = cur.next
		if even_head:
			head = even_head
			even_tail.next = odd_head
		else:
			head = odd_head
		if odd_tail:
			odd_tail.next = None
		return head


class Solution:

	def divide(self, N, head):
		curr = head
		(eh, et) = (None, None)
		(oh, ot) = (None, None)
		while curr is not None:
			next_node = curr.next
			curr.next = None
			if curr.data % 2 == 0:
				if eh == None and et == None:
					eh = curr
					et = curr
				et.next = curr
				et = et.next
			else:
				if oh == None and ot == None:
					oh = curr
					ot = curr
				ot.next = curr
				ot = ot.next
			curr = next_node
		if ot != None:
			ot.next = None
		if et != None:
			et.next = None
		if oh is None and ot is None:
			return eh
		elif eh is None and et is None:
			return oh
		else:
			et.next = oh
			return eh


class Solution:

	def divide(self, N, head):
		temp = head
		even = []
		odd = []
		while temp:
			if temp.data % 2 == 0:
				even.append(temp.data)
				temp = temp.next
			else:
				odd.append(temp.data)
				temp = temp.next
		res = even + odd
		cur = head
		for i in res:
			cur.data = i
			cur = cur.next
		return head


class Solution:

	def divide(self, N, head):
		even = None
		odd = None
		head2 = None
		p = head
		while p != None:
			temp = p.next
			p.next = None
			if p.data % 2 == 0:
				if even == None:
					even = p
					head = even
				else:
					even.next = p
					even = even.next
			elif odd == None:
				odd = p
				head2 = odd
			else:
				odd.next = p
				odd = odd.next
			p = temp
		if even:
			even.next = head2
			return head
		else:
			return head2


class Solution:

	def divide(self, N, head):
		odd = None
		even = None
		(curr_o, curr_e) = (odd, even)
		while head is not None:
			if head.data & 1 == 1:
				if curr_o is None:
					odd = head
				else:
					curr_o.next = head
				curr_o = head
			else:
				if curr_e is None:
					even = head
				else:
					curr_e.next = head
				curr_e = head
			head = head.next
		if even is None:
			return odd
		curr_e.next = odd
		if curr_o is not None:
			curr_o.next = None
		return even


class Solution:

	def divide(self, N, head):
		evenStart = None
		evenEnd = None
		oddStart = None
		oddEnd = None
		curr = head
		while curr:
			if curr.data % 2 == 0:
				if evenStart:
					evenEnd.next = curr
					evenEnd = evenEnd.next
				else:
					evenEnd = curr
					evenStart = curr
			elif oddStart:
				oddEnd.next = curr
				oddEnd = oddEnd.next
			else:
				oddStart = curr
				oddEnd = curr
			curr = curr.next
		if oddEnd:
			oddEnd.next = None
		if evenStart:
			evenEnd.next = oddStart
		else:
			evenStart = oddStart
		return evenStart


class Solution:

	def divide(self, N, head):
		estart = None
		eend = None
		oend = None
		ostart = None
		curr = head
		while curr != None:
			if curr.data % 2 == 0:
				if estart == None:
					estart = curr
					eend = estart
				else:
					eend.next = curr
					eend = eend.next
			elif ostart == None:
				ostart = curr
				oend = ostart
			else:
				oend.next = curr
				oend = oend.next
			curr = curr.next
		if ostart == None:
			return estart
		if estart == None:
			return ostart
		eend.next = ostart
		oend.next = None
		return estart


class Solution:

	def divide(self, N, head):
		even = []
		odd = []
		h = head
		while h:
			if h.data % 2 == 0:
				even.append(h.data)
			else:
				odd.append(h.data)
			h = h.next
		llist = even + odd
		h = head
		i = 0
		while h:
			h.data = llist[i]
			i += 1
			h = h.next
		return head


class Node:

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

class Solution:

	def divide(self, N, head):
		even = Node(0)
		odd = Node(0)
		n1 = even
		n2 = odd
		n = head
		while n is not None:
			new_node = Node(n.data)
			if n.data % 2 == 0:
				n1.next = new_node
				n1 = n1.next
			else:
				n2.next = new_node
				n2 = n2.next
			n = n.next
		n1.next = odd.next
		return even.next


class Node:

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

class Solution:

	def divide(self, N, head):
		(even_head, odd_head) = (None, None)
		(even_tail, odd_tail) = (None, None)
		curr = head
		while curr:
			if curr.data % 2 == 0:
				if not even_head:
					even_head = curr
					even_tail = curr
				else:
					even_tail.next = curr
					even_tail = even_tail.next
			elif not odd_head:
				odd_head = curr
				odd_tail = curr
			else:
				odd_tail.next = curr
				odd_tail = odd_tail.next
			curr = curr.next
		if even_head:
			head = even_head
			even_tail.next = odd_head
		else:
			head = odd_head
		if odd_tail:
			odd_tail.next = None
		return head


class Solution:

	def divide(self, N, head):
		(odd, even) = (None, None)
		(ot, et) = (None, None)
		curr = head
		while curr:
			if curr.data & 1:
				if odd is None:
					(ot, odd) = (curr, curr)
				else:
					ot.next = curr
					ot = curr
			elif even is None:
				(et, even) = (curr, curr)
			else:
				et.next = curr
				et = curr
			curr = curr.next
		if even:
			head = even
			et.next = odd
		else:
			head = odd
		if ot:
			ot.next = None
		return head


class Solution:

	def divide(self, N, head):
		ods = ode = None
		evens = evene = None
		curr = head
		while curr != None:
			x = curr.data
			if x % 2 == 0:
				if evens is None:
					evens = curr
					evene = evens
				else:
					evene.next = curr
					evene = evene.next
			elif ods is None:
				ods = curr
				ode = ods
			else:
				ode.next = curr
				ode = ode.next
			curr = curr.next
		if ods is None or evens is None:
			return head
		evene.next = ods
		ode.next = None
		head = evens
		return head


class Solution:

	def divide(self, N, head):
		even = node()
		odd = node()
		temp1 = even
		temp2 = odd
		while head:
			temp3 = head.next
			head.next = None
			if head.data % 2 == 0:
				temp1.next = head
				temp1 = temp1.next
			else:
				temp2.next = head
				temp2 = temp2.next
			head = temp3
		temp1.next = odd.next
		return even.next


class Solution:

	def divide(self, N, head):
		evenhead = node()
		oddhead = node()
		t_even = evenhead
		t_odd = oddhead
		while head is not None:
			if head.data % 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
		if t_even.data is None:
			return oddhead.next
		if t_odd.data is None:
			return evenhead.next
		t_even.next = oddhead.next
		return evenhead.next


class Solution:

	def divide(self, N, head):
		a = []
		b = []
		c = []
		while head != None:
			a.append(head.data)
			head = head.next
		for i in a:
			if i % 2 == 0:
				b.append(i)
			else:
				c.append(i)
		x = b + c
		for j in x:
			print(j, end=' ')


class Node:

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

class Solution:

	def divide(self, N, head):
		c = d = Node()
		a = b = Node()
		ptr = head
		while ptr:
			if ptr.data % 2 == 0:
				b.next = ptr
				b = b.next
			else:
				d.next = ptr
				d = d.next
			ptr = ptr.next
		b.next = c.next
		d.next = None
		return a.next


class Solution:

	def divide(self, n, head):
		a = head
		while a.next != None:
			a = a.next
		count = 0
		prev = None
		cur = head
		front = cur.next
		flag = 0
		while count < n:
			if cur.data % 2 == 1:
				a.next = cur
				a = cur
				cur.next = None
				cur = front
				if prev != None:
					prev.next = cur
				if front != None and front.next != None:
					front = front.next
			else:
				if flag == 0:
					head = cur
					flag = 1
				prev = cur
				cur = cur.next
				if front != None and front.next != None:
					front = front.next
			count += 1
		return head


class Solution:

	def divide(self, N, head):
		occ_e = None
		occ_o = None
		itr = head
		while itr:
			if itr.data % 2 != 0:
				occ_o = itr
				itr = itr.next
			elif occ_o is not None:
				if occ_e is None:
					occ_o.next = itr.next
					itr.next = head
					occ_e = itr
					head = occ_e
					itr = occ_o.next
				else:
					occ_o.next = itr.next
					itr.next = occ_e.next
					occ_e.next = itr
					occ_e = itr
					itr = occ_o.next
			elif occ_e is None:
				occ_e = itr
				head = occ_e
				itr = itr.next
			else:
				occ_e = occ_e.next
				itr = itr.next
		return head


class Solution:

	def divide(self, N, head):
		even = odd = None
		etmp = otmp = None
		while head:
			if head.data % 2 == 0:
				if not even:
					etmp = head
					even = head
				else:
					even.next = head
					even = even.next
			elif not odd:
				otmp = head
				odd = head
			else:
				odd.next = head
				odd = odd.next
			head = head.next
		if odd:
			odd.next = None
		if even:
			even.next = otmp
		else:
			etmp = otmp
		return etmp


class Node:

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

class Solution:

	def divide(self, N, head):
		end = head
		prev = None
		curr = head
		while end.next != None:
			end = end.next
		new_end = end
		while curr.data % 2 != 0 and curr != end:
			new_end.next = curr
			curr = curr.next
			new_end.next.next = None
			new_end = new_end.next
		if curr.data % 2 == 0:
			head = curr
			while curr != end:
				if curr.data % 2 == 0:
					prev = curr
					curr = curr.next
				else:
					prev.next = curr.next
					curr.next = None
					new_end.next = curr
					new_end = curr
					curr = prev.next
		else:
			prev = curr
		if new_end != end and end.data % 2 != 0:
			prev.next = end.next
			end.next = None
			new_end.next = end
		return head


class Solution:

	def divide(self, N, head):
		curr = head
		count = 0
		while curr.next:
			count += 1
			curr = curr.next
		last_point = curr
		curr = head
		n = count + 1
		if n <= 1:
			return head
		count = 0
		prev = None
		while count < n:
			if curr.data % 2 != 0:
				if curr.next:
					if prev == None:
						head = curr.next
					else:
						prev.next = curr.next
				last_point.next = curr
				last_point = curr
				curr = curr.next
				last_point.next = None
			else:
				if prev == None:
					head = curr
				else:
					prev.next = curr
				prev = curr
				curr = curr.next
			count += 1
		return head


class Solution:

	def divide(self, N, head):
		if not head or not head.next:
			return head
		even_start = None
		even_end = None
		odd_start = None
		odd_end = None
		curr = head
		while curr:
			if not curr.data % 2:
				if even_start:
					even_end.next = curr
					even_end = even_end.next
				else:
					even_start = curr
					even_end = even_start
			elif odd_start:
				odd_end.next = curr
				odd_end = odd_end.next
			else:
				odd_start = curr
				odd_end = odd_start
			curr = curr.next
		if not even_start or not odd_start:
			return head
		even_end.next = odd_start
		odd_end.next = None
		return even_start


class Solution:

	def divide(self, N, head):
		(temp, curr) = (head, head)
		(array, array1) = ([], [])
		while temp:
			if temp.data % 2 == 0:
				array.append(temp.data)
			else:
				array1.append(temp.data)
			temp = temp.next
		array[:] = array[:] + array1[:]
		for x in range(N):
			curr.data = array[x]
			curr = curr.next
		return head


class Solution:

	def reverse(self, head):
		pre = None
		cur = head
		while cur is not None:
			t = pre
			pre = cur
			cur = cur.next
			pre.next = t
		return pre

	def divide(self, N, head):
		es = False
		cur = head
		pre = None
		while cur is not None:
			if cur.data & 1:
				break
			else:
				es = True
				pre = cur
				cur = cur.next
		eh = head
		ee = pre
		if cur is None:
			return head
		head = cur
		pre = None
		ne = None
		b = False
		while cur is not None:
			if cur.data & 1:
				pre = cur
				cur = cur.next
			else:
				b = True
				if pre:
					pre.next = cur.next
					cur.next = head
					head = cur
					cur = pre.next
				else:
					cur = cur.next
		if not b and es is False:
			return head
		cur = head
		pre = None
		if cur.next is None:
			if es is True:
				ee.next = cur
				return eh
			return head
		flag = False
		while cur is not None:
			if cur.data % 2 == 0:
				flag = True
				pre = cur
				cur = cur.next
			else:
				break
		if flag:
			pre.next = None
			t = self.reverse(head)
			head.next = cur
			if es:
				ee.next = t
				return eh
			return t
		elif es:
			ee.next = head
			return eh
		else:
			return head


class Solution:

	def divide(self, N, head):
		z = head
		while z.next != None:
			z = z.next
		if z == head:
			return head
		app = z
		u = head
		flag = 0
		d = None
		p = node()
		p.next = head
		prev = p
		curr = p.next
		u = curr
		while u != None:
			if u == d:
				break
			if u.data % 2 != 0:
				if flag == 0:
					if app == u:
						break
					flag = 1
					d = u
					prev.next = u.next
					app.next = u
					app = u
					app.next = None
					u = prev.next
				else:
					if app == u:
						break
					prev.next = u.next
					app.next = u
					app = u
					app.next = None
					u = prev.next
			elif u.data % 2 == 0:
				u = u.next
				prev = prev.next
			if u == None:
				break
		return p.next


class Solution:

	def divide(self, N, head):
		evenstart = None
		evenend = None
		oddstart = None
		oddend = None
		curr = head
		while curr is not None:
			value = curr.data
			if value % 2 == 0:
				if evenstart == None:
					evenstart = curr
					evenend = evenstart
				else:
					evenend.next = curr
					evenend = evenend.next
			elif oddstart == None:
				oddstart = curr
				oddend = oddstart
			else:
				oddend.next = curr
				oddend = oddend.next
			curr = curr.next
		if oddstart == None or evenstart == None:
			return head
		evenend.next = oddstart
		oddend.next = None
		head = evenstart
		return head


class Solution:

	def divide(self, N, head):
		evenStart = None
		evenEnd = None
		oddStart = None
		oddEnd = None
		currNode = head
		while currNode != None:
			val = currNode.data
			if val % 2 == 0:
				if evenStart == None:
					evenStart = currNode
					evenEnd = evenStart
				else:
					evenEnd.next = currNode
					evenEnd = evenEnd.next
			elif oddStart == None:
				oddStart = currNode
				oddEnd = oddStart
			else:
				oddEnd.next = currNode
				oddEnd = oddEnd.next
			currNode = currNode.next
		if oddStart == None or evenStart == None:
			return head
		evenEnd.next = oddStart
		oddEnd.next = None
		head = evenStart
		return head


class Solution:

	def divide(self, N, head):
		if not head:
			return None
		even_head = None
		even_tail = None
		odd_head = None
		odd_tail = None
		current = head
		while current:
			if current.data % 2 == 0:
				if not even_head:
					even_head = current
					even_tail = current
				else:
					even_tail.next = current
					even_tail = even_tail.next
			elif not odd_head:
				odd_head = current
				odd_tail = current
			else:
				odd_tail.next = current
				odd_tail = odd_tail.next
			current = current.next
		if even_tail:
			even_tail.next = odd_head
		if odd_tail:
			odd_tail.next = None
		return even_head if even_head else odd_head


class Solution:

	def divide(self, N, head):
		oddh = None
		oddt = None
		evenh = None
		event = None
		while head:
			if head.data % 2 != 0:
				if oddh is None:
					oddh = head
					oddt = head
					head = head.next
				else:
					oddt.next = head
					oddt = oddt.next
					head = head.next
			elif evenh is None:
				evenh = head
				event = head
				head = head.next
			else:
				event.next = head
				event = event.next
				head = head.next
		if oddh is None:
			return evenh
		if evenh is None:
			return oddh
		event.next = oddh
		oddt.next = None
		return evenh


class Solution:

	def divide(self, N, head):
		a = []
		b = []
		cur = head
		i = 0
		while cur != None:
			if cur.data % 2 == 0:
				a.append(cur.data)
				cur = cur.next
			else:
				b.append(cur.data)
				cur = cur.next
		a = a + b
		cur = head
		while cur != None:
			cur.data = a[i]
			i += 1
			cur = cur.next
		return head


class Solution:

	def divide(self, N, head):
		(even, odd, first_even, first_odd, first_node) = (None, None, None, None, None)
		curr = head
		while curr:
			if curr.data % 2 == 0:
				if not even:
					first_even = curr
				else:
					even.next = curr
				even = curr
				if not first_node:
					first_node = 'even'
			else:
				if not odd:
					first_odd = curr
				else:
					odd.next = curr
				odd = curr
				if not first_node:
					first_node = 'odd'
			curr = curr.next
		if first_even:
			head = first_even
			even.next = first_odd
		else:
			head = first_odd
		if first_odd:
			odd.next = None
		return head


class Solution:

	def divide(self, N, head):
		even_head = even_tail = node()
		odd_head = odd_tail = node()
		while head:
			if head.data % 2 == 0:
				even_tail.next = head
				head = head.next
				even_tail = even_tail.next
			else:
				odd_tail.next = head
				head = head.next
				odd_tail = odd_tail.next
		even_tail.next = odd_head.next
		odd_tail.next = None
		return even_head.next


class Solution:

	def divide(self, N, head):
		even = []
		odd = []
		while head:
			if head.data % 2 == 0:
				even.append(head.data)
			else:
				odd.append(head.data)
			head = head.next
		ans = Linked_List()
		for i in even:
			ans.insert(i)
		for i in odd:
			ans.insert(i)
		return ans.head


class Solution:

	def divide(self, N, head):
		if head.next is None:
			return head
		ES = None
		EE = None
		OS = None
		OE = None
		currNode = head
		while currNode != None:
			val = currNode.data
			if val % 2 == 0:
				if ES == None:
					ES = currNode
					EE = ES
				else:
					EE.next = currNode
					EE = EE.next
			elif OS == None:
				OS = currNode
				OE = OS
			else:
				OE.next = currNode
				OE = OE.next
			currNode = currNode.next
		if OS == None:
			return ES
		if ES == None:
			return OS
		else:
			EE.next = OS
			OE.next = None
			head = ES
			return head


class Solution:

	def divide(self, n, head):
		h = head
		a = node()
		r = a
		b = node()
		r1 = b
		while h:
			if h.data % 2 == 0:
				a.next = node()
				a.next.data = h.data
				a = a.next
			else:
				b.next = node()
				b.next.data = h.data
				b = b.next
			h = h.next
		a.next = r1.next
		return r.next


class Solution:

	def divide(self, N, head):
		list = []
		curr = head
		while curr:
			list.append(curr.data)
			curr = curr.next
		list1 = []
		list2 = []
		for i in list:
			if i % 2 == 0:
				list1.append(i)
			else:
				list2.append(i)
		x = list1 + list2
		for i in x:
			print(i, end=' ')


class Node:

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

class Solution:

	def divide(self, N, head):
		o = []
		e = []
		n = head
		while n is not None:
			if n.data % 2 == 0:
				e += [n.data]
			else:
				o += [n.data]
			n = n.next
		r = e + o
		head1 = None
		head1 = Node(r[0])
		n = head1
		for i in range(1, N):
			no = Node(r[i])
			n.next = no
			no.next = None
			n = n.next
		return head1


class Solution:

	def divide(self, N, head):
		even = None
		odd = None
		e_head = None
		o_head = None
		while head is not None:
			if head.data % 2 != 0:
				if o_head == None:
					odd = head
					o_head = head
				else:
					odd.next = head
					odd = odd.next
			elif e_head == None:
				even = head
				e_head = head
			else:
				even.next = head
				even = even.next
			head = head.next
		if o_head == None and e_head != None:
			even.next = None
			return e_head
		elif e_head == None and o_head != None:
			odd.next = None
			return o_head
		elif o_head != None and e_head != None:
			even.next = o_head
			odd.next = None
			return e_head


class Solution:

	def divide(self, N, head):
		temp = head
		temp1 = head
		if head.data % 2 == 0:
			while temp != None and temp.data % 2 == 0:
				temp1 = temp
				temp = temp.next
			tp = temp1
		else:
			tp = head
			temp = head.next
			while temp != None and tp.data % 2 != 0:
				if temp.data % 2 == 0:
					tp.next = temp.next
					temp.next = head
					head = temp
					temp = tp.next
					break
				else:
					tp = temp
					temp = temp.next
			temp1 = head
		while temp != None:
			if temp.data % 2 == 0:
				tp.next = temp.next
				temp.next = temp1.next
				temp1.next = temp
				temp1 = temp
				temp = tp.next
			else:
				tp = temp
				temp = temp.next
		return head


class Solution:

	def divide(self, N, head):
		k = []
		h = head
		l = []
		while h:
			if h.data % 2 == 0:
				k.append(h.data)
			else:
				l.append(h.data)
			h = h.next
		h = head
		i = 0
		while i < len(k):
			h.data = k[i]
			i += 1
			h = h.next
		i = 0
		while i < len(l):
			h.data = l[i]
			i += 1
			h = h.next
		return head


class Solution:

	def divide(self, N, head):
		li = []
		e = head
		o = head
		while e:
			if e.data % 2 == 0:
				li.append(e.data)
			e = e.next
		while o:
			if o.data % 2 != 0:
				li.append(o.data)
			o = o.next
		ans = None
		t = None
		for i in li:
			print(i, end=' ')
		return ans


class Solution:

	def divide(self, N, head):
		first_even = None
		first_odd = None
		last_even = None
		last_odd = None
		curr = head
		while curr:
			if curr.data % 2 != 0:
				if first_even == None:
					first_even = curr
				last_even = curr
			else:
				if first_odd == None:
					first_odd = curr
				if first_even:
					last_even.next = curr.next
					if last_odd:
						last_odd.next = curr
					last_odd = curr
					last_odd.next = first_even
				else:
					last_odd = curr
			if last_even:
				curr = last_even.next
			else:
				curr = last_odd.next
		if first_odd:
			return first_odd
		return first_even


class Solution:

	def divide(self, N, head):
		if not head or not head.next:
			return head
		even = None
		odd = None
		even_tail = None
		odd_tail = None
		curr = head
		while curr:
			if curr.data % 2 == 0:
				if not even:
					even = curr
					even_tail = even
				else:
					even_tail.next = curr
					even_tail = even_tail.next
			elif not odd:
				odd = curr
				odd_tail = odd
			else:
				odd_tail.next = curr
				odd_tail = odd_tail.next
			curr = curr.next
		if not even:
			return odd
		else:
			even_tail.next = odd
			if odd_tail:
				odd_tail.next = None
			return even


class Solution:

	def divide(self, N, head):
		(odd, even) = ([], [])
		temp = head
		while temp is not None:
			if temp.data % 2 == 0:
				even.append(temp.data)
			else:
				odd.append(temp.data)
			temp = temp.next
		for i in range(0, len(even)):
			print(even[i], end=' ')
		for i in range(0, len(odd)):
			print(odd[i], end=' ')


class Solution:

	def divide(self, N, head):
		even = None
		odd = None
		curr = head
		(heven, hodd) = (None, None)
		while curr is not None:
			if curr.data % 2 == 0:
				if even == None:
					even = curr
					heven = even
				else:
					even.next = curr
					even = curr
			elif odd == None:
				odd = curr
				hodd = odd
			else:
				odd.next = curr
				odd = curr
			curr = curr.next
		if odd == None:
			return heven
		if even == None:
			return hodd
		odd.next = None
		even.next = hodd
		return heven


class Solution:

	def divide(self, N, head):
		cntodd = 0
		cnteve = 0
		evebeg = None
		oddbeg = None
		eveend = None
		oddend = None
		x = head
		while x:
			if x.data % 2 == 0:
				if cnteve == 0:
					evebeg = x
					cnteve += 1
				if eveend:
					eveend.next = x
				eveend = x
			else:
				if cntodd == 0:
					oddbeg = x
					cntodd += 1
				if oddend:
					oddend.next = x
				oddend = x
			x = x.next
		if evebeg != None:
			head = evebeg
		else:
			head = oddbeg
		if eveend != None:
			eveend.next = oddbeg
		if oddend != None:
			oddend.next = None
		return head


class Solution:

	def divide(self, N, head):
		odd = even = curr = None
		new_odd = new_even = None
		while head:
			data = head.data
			if data % 2 == 1:
				if not new_odd:
					new_odd = odd = head
				else:
					odd.next = head
					odd = head
			elif not new_even:
				new_even = even = head
			else:
				even.next = head
				even = head
			head = head.next
		if even:
			even.next = new_odd
		if odd:
			odd.next = None
		if new_even:
			return new_even
		return new_odd


class Solution:

	def divide(self, N, head):
		odd = oddHead = node()
		even = evenHead = node()
		nxt = head
		while nxt:
			if nxt.data % 2 == 0:
				even.next = nxt
				even = nxt
				nxt = nxt.next
			else:
				odd.next = nxt
				odd = nxt
				nxt = nxt.next
		even.next = oddHead.next
		odd.next = None
		return evenHead.next


class Solution:

	def divide(self, N, head):
		curr = head
		even = even_t = odd = odd_t = None
		while curr:
			if curr.data % 2 == 0:
				if even is None:
					even = even_t = curr
				else:
					even_t.next = curr
					even_t = even_t.next
			elif odd is None:
				odd = odd_t = curr
			else:
				odd_t.next = curr
				odd_t = odd_t.next
			curr = curr.next
		if even is None:
			odd_t.next = None
			return odd
		if odd is None:
			even_t.next = None
			return even
		if odd and even:
			even_t.next = odd
			odd_t.next = None
			return even


class Solution:

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


class Solution:

	def divide(self, N, head):
		curr = None
		s = head
		odd = []
		eve = []
		while s:
			if s.data % 2 == 0:
				eve.append(s.data)
			else:
				odd.append(s.data)
			s = s.next
		s = head
		while eve:
			s.data = eve.pop(0)
			s = s.next
		while odd:
			s.data = odd.pop(0)
			s = s.next
		return head


class Solution:

	def divide(self, N, head):
		l = []
		m = []
		p = head
		while p:
			if p.data % 2 == 0:
				l.append(p.data)
			else:
				m.append(p.data)
			p = p.next
		i = 0
		l.extend(m)
		ll = Linked_List()
		for i in l:
			ll.insert(i)
		return ll.head


class Solution:

	def divide(self, N, head):
		t = head
		e = []
		o = []
		while t:
			if t.data % 2 == 0:
				e.append(t.data)
			elif t.data % 2 != 0:
				o.append(t.data)
			t = t.next
		x = head
		if len(e) == 0 or len(o) == 0:
			return head
		else:
			result = e + o
			for i in range(N):
				x.data = result[i]
				x = x.next
			return head


class Solution:

	def divide(self, N, head):
		oh = None
		ot = None
		eh = None
		et = None
		while head:
			if head.data % 2 == 0:
				if eh == None:
					et = head
					eh = head
					head = head.next
				else:
					et.next = head
					et = et.next
					head = head.next
			elif oh == None:
				ot = head
				oh = head
				head = head.next
			else:
				ot.next = head
				ot = ot.next
				head = head.next
		if eh is None:
			return oh
		elif oh is None:
			return eh
		else:
			et.next = oh
			ot.next = None
			return eh


class Solution:

	def divide(self, N, head):
		n = head
		oddTempTemp = None
		ptr_O = None
		evenTempTemp = None
		ptr_E = None
		while n != None:
			if n.data % 2 != 0:
				if ptr_O == None:
					oddTemp = n
					ptr_O = n
				else:
					oddTemp.next = n
					oddTemp = oddTemp.next
			elif ptr_E == None:
				evenTemp = n
				ptr_E = n
			else:
				evenTemp.next = n
				evenTemp = evenTemp.next
			n = n.next
		if ptr_O == None and ptr_E != None:
			evenTemp.next = None
			return ptr_E
		elif ptr_E == None and ptr_O != None:
			oddTemp.next = None
			return ptr_O
		elif ptr_O != None and ptr_E != None:
			evenTemp.next = ptr_O
			oddTemp.next = None
			return ptr_E


class Solution:

	def divide(self, N, head):
		l1 = []
		l2 = []
		l3 = []
		l4 = []
		while head:
			l1.append(head.data)
			head = head.next
		for i in l1:
			if i % 2 == 0:
				l2.append(i)
			if i % 2 != 0:
				l3.append(i)
		l4 = l2 + l3
		for i in l4:
			print(i, end=' ')


class Solution:

	def divide(self, N, head):
		(ehead, etail, ohead, otail) = (None, None, None, None)
		temp = head
		while temp:
			if temp.data % 2 == 0:
				if ehead == None:
					ehead = temp
					etail = temp
				else:
					etail.next = temp
					etail = temp
			elif ohead == None:
				ohead = temp
				otail = temp
			else:
				otail.next = temp
				otail = temp
			temp = temp.next
		if ehead == None:
			return ohead
		if ohead == None:
			return ehead
		etail.next = ohead
		otail.next = None
		return ehead


class Solution:

	def divide(self, N, head):
		arr = []
		n = head
		while n is not None:
			arr.append(n.data)
			n = n.next
		a = []
		b = []
		for i in arr:
			if i % 2 == 0:
				a.append(i)
			else:
				b.append(i)
		for j in b:
			a.append(j)
		head = None
		tail = None
		for i in range(len(a)):
			if head == None:
				head = node()
				head.data = a[i]
				tail = head
			else:
				tail.next = node()
				tail.next.data = a[i]
				tail = tail.next
		return head


class Solution:

	def divide(self, N, head):
		lastEven = None
		curr = head
		currPrev = None
		while curr:
			if curr.data % 2 == 0:
				node = curr
				if currPrev and currPrev != lastEven:
					currPrev.next = node.next
					curr = currPrev
				else:
					lastEven = node
				if lastEven and node != lastEven:
					nxt = lastEven.next
					lastEven.next = node
					node.next = nxt
					lastEven = node
				if not lastEven:
					node.next = head
					head = node
					lastEven = node
			currPrev = curr
			curr = curr.next
		return head


class Solution:

	def divide(self, N, head):
		cur = head
		cur1 = head
		dummy = cur1
		li = []
		while cur:
			if cur.data % 2 == 0:
				cur1.data = cur.data
				cur1 = cur1.next
			else:
				li.append(cur.data)
			cur = cur.next
		for i in range(len(li)):
			cur1.data = li[i]
			cur1 = cur1.next
		return dummy


class Solution:

	def divide(self, N, head):
		odd = preo = node()
		even = pree = node()
		cur = head
		while cur:
			if cur.data % 2 == 0:
				pree.next = cur
				pree = pree.next
			else:
				preo.next = cur
				preo = preo.next
			cur = cur.next
			pree.next = odd.next
			preo.next = None
		return even.next


class Solution:

	def divide(self, N, head):
		odd = prevo = node()
		even = prev = node()
		temp = head
		while temp:
			if temp.data % 2 != 0:
				prevo.next = temp
				prevo = prevo.next
			else:
				prev.next = temp
				prev = prev.next
			temp = temp.next
		prev.next = odd.next
		prevo.next = None
		return even.next


class Node:

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

class Solution:

	def divide(self, N, head):
		prev = None
		pe = head
		heado = Node(-1)
		po = heado
		while pe != None:
			if pe.data % 2 != 0:
				po.next = pe
				po = po.next
				if prev == None:
					a = pe.next
					pe.next = None
					pe = a
					head = pe
				else:
					a = pe.next
					pe.next = None
					prev.next = a
					pe = a
			else:
				prev = pe
				pe = pe.next
		if head == None:
			return heado.next
		if heado.next != 0:
			heado = heado.next
			prev.next = heado
		return head


class Solution:

	def divide(self, N, head):
		if head == None or head.next == None:
			return head
		last = head
		cu = 1
		while last.next:
			last = last.next
			cu += 1
		till = last
		temp = head
		prev = None
		cou = 1
		while cou <= cu:
			if temp.data % 2 != 0:
				if prev == None:
					head = head.next
					temp.next = None
					last.next = temp
					last = temp
					temp = head
				elif temp.next == None:
					break
				else:
					prev.next = temp.next
					temp.next = None
					last.next = temp
					last = temp
					temp = prev.next
			else:
				prev = temp
				temp = temp.next
			cou += 1
		return head


class Solution:

	def divide(self, N, head):
		self.curr = head
		evstart = None
		evend = None
		odstart = None
		odend = None
		while self.curr:
			if self.curr.data % 2 == 0:
				if evstart == None:
					evstart = self.curr
					evend = self.curr
				else:
					evend.next = self.curr
					evend = evend.next
			elif odstart == None:
				odstart = self.curr
				odend = self.curr
			else:
				odend.next = self.curr
				odend = odend.next
			self.curr = self.curr.next
		if odstart == None:
			evend.next = None
			return evstart
		elif evstart == None:
			odend.next = None
			return odstart
		else:
			evend.next = odstart
			odend.next = None
			return evstart


class Solution:

	def divide(self, N, head):
		even_end = None
		odd_end = None
		odd_head = None
		even_head = None
		p = head
		while p:
			if p.data % 2 == 0:
				if not even_head:
					even_head = p
				if even_end:
					even_end.next = p
				even_end = p
				q = p.next
				if odd_end:
					odd_end.next = q
				even_end.next = None
				p = q
			else:
				if not odd_head:
					odd_head = p
				odd_end = p
				p = p.next
		if even_head:
			even_end.next = odd_head
			return even_head
		else:
			return odd_head


class Solution:

	def divide(self, N, head):
		temp = head
		odd_head = odd = None
		even_head = even = None
		while temp is not None:
			if temp.data % 2 != 0:
				if odd_head is None:
					odd_head = temp
					odd = temp
				else:
					odd.next = temp
					odd = odd.next
			elif even_head is None:
				even = temp
				even_head = temp
			else:
				even.next = temp
				even = even.next
			temp = temp.next
		if odd_head is None and even_head is not None:
			even.next = None
			return even_head
		elif even_head is None and odd_head is not None:
			odd.next = None
			return odd_head
		elif odd_head is not None and even_head is not None:
			even.next = odd_head
			odd.next = None
			return even_head


class Solution:

	def divide(self, N, head):
		ocurr = head
		ecurr = head
		curr = head
		while curr and curr.data % 2 == 0:
			curr = curr.next
		ocurr = curr
		eprev = None
		curr = head
		while curr and curr.data % 2 != 0:
			eprev = curr
			curr = curr.next
		ecurr = curr
		curr = ecurr
		if curr == None:
			return ocurr
		while curr:
			if curr.data % 2 == 1:
				if eprev is None:
					eprev = curr
				else:
					eprev.next = curr
					eprev = curr
				prev.next = curr.next
			else:
				prev = curr
			curr = curr.next
		prev.next = ocurr
		if eprev:
			eprev.next = None
		return ecurr