Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.
Example 1:
Input:
N = 8
value[] = {1,2,2,1,2,0,2,2}
Output: 0 1 1 2 2 2 2 2
Explanation: All the 0s are segregated
to the left end of the linked list,
2s to the right end of the list, and
1s in between.
Example 2:
Input:
N = 4
value[] = {2,2,0,1}
Output: 0 1 2 2
Explanation: After arranging all the
0s,1s and 2s in the given format,
the output will be 0 1 2 2.
Your Task:
The task is to complete the function segregate() which segregates the nodes in the linked list as asked in the problem statement and returns the head of the modified linked list. The printing is done automatically by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{3}

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

Starter code:
#User function Template for python3

'''

	Your task is to segregate the list of 

	0s,1s and 2s.

	

	Function Arguments: head of the original list.

	Return Type: head of the new list formed.



	{

		# Node Class

		class Node:

		    def __init__(self, data):   # data -> value stored in node

		        self.data = data

		        self.next = None

	}



'''

class Solution:

    #Function to sort a linked list of 0s, 1s and 2s.

    def segregate(self, head):

        #code here

    

Solutions:
class Solution:

	def segregate(self, head):
		zeros = 0
		ones = 0
		twos = 0
		temp = head
		curr = head
		while curr:
			if curr.data == 0:
				zeros += 1
			if curr.data == 1:
				ones += 1
			if curr.data == 2:
				twos += 1
			curr = curr.next
		new = Node(0)
		t = new
		while temp:
			if zeros != 0:
				new.next = Node(0)
				zeros -= 1
			elif ones != 0:
				new.next = Node(1)
				ones -= 1
			elif twos != 0:
				new.next = Node(2)
				twos -= 1
			temp = temp.next
			new = new.next
		return t.next


class Solution:

	def segregate(self, head):
		zero_count = 0
		one_count = 0
		two_count = 0
		(new_head, return_head) = (head, head)
		while head != None:
			if head.data == 0:
				zero_count += 1
			elif head.data == 1:
				one_count += 1
			else:
				two_count += 1
			head = head.next
		while zero_count != 0:
			new_head.data = 0
			new_head = new_head.next
			zero_count -= 1
		while one_count != 0:
			new_head.data = 1
			new_head = new_head.next
			one_count -= 1
		while two_count != 0:
			new_head.data = 2
			new_head = new_head.next
			two_count -= 1
		return return_head


class Solution:

	def segregate(self, head):
		(one, two, three) = (Node(-1), Node(-1), Node(-1))
		(refone, reftwo, refthree) = (one, two, three)
		tailone = tailtwo = tailthree = None
		while head:
			if head.data == 0:
				one.next = head
				one = one.next
				tailone = one
			if head.data == 1:
				two.next = head
				two = two.next
				tailtwo = two
			if head.data == 2:
				three.next = head
				three = three.next
				tailthree = three
			head = head.next
		refone = refone.next
		reftwo = reftwo.next
		refthree = refthree.next
		if tailthree:
			tailthree.next = None
		if reftwo:
			tailtwo.next = refthree
		if refone:
			if reftwo:
				tailone.next = reftwo
			else:
				tailone.next = refthree
		else:
			if reftwo:
				return reftwo
			return refthree
		return refone


class Solution:

	def segregate(self, head):
		a = 0
		b = 0
		c = 0
		n = 0
		temp = head
		while temp != None:
			if temp.data == 0:
				a += 1
			elif temp.data == 1:
				b += 1
			else:
				c += 1
			temp = temp.next
			n += 1
		temp = head
		for i in range(a):
			temp.data = 0
			temp = temp.next
		for i in range(b):
			temp.data = 1
			temp = temp.next
		for i in range(c):
			temp.data = 2
			temp = temp.next
		return head


class Solution:

	def segregate(self, head):
		count0 = 0
		count1 = 0
		count2 = 0
		itr = head
		while itr:
			if itr.data == 0:
				count0 += 1
			if itr.data == 1:
				count1 += 1
			if itr.data == 2:
				count2 += 1
			itr = itr.next
		itr2 = head
		i = 0
		while itr2:
			if i < count0:
				itr2.data = 0
			if count0 <= i < count1 + count0:
				itr2.data = 1
			if count0 + count1 <= i < count2 + count1 + count0:
				itr2.data = 2
			itr2 = itr2.next
			i += 1
		itr3 = head
		return itr3


class Solution:

	def segregate(self, head):
		d = {0: 0, 1: 0, 2: 0}
		cur = head
		while cur is not None:
			d[cur.data] += 1
			cur = cur.next
		cur = head
		while cur is not None:
			if d[0]:
				cur.data = 0
				d[0] -= 1
			elif d[1]:
				cur.data = 1
				d[1] -= 1
			elif d[2]:
				cur.data = 2
				d[2] -= 1
			cur = cur.next
		return head


class Solution:

	def segregate(self, head):
		l = []
		ptr = head
		while ptr != None:
			l.append(ptr.data)
			ptr = ptr.next
		l.sort()
		ptr = head
		for i in l:
			ptr.data = i
			ptr = ptr.next
		return head


class Solution:

	def segregate(self, head):
		if not head:
			return head
		fast = slow = head
		while fast:
			if fast.data == 0:
				fast.data = slow.data
				slow.data = 0
				slow = slow.next
			fast = fast.next
		fast = slow
		while fast:
			if fast.data == 1:
				fast.data = slow.data
				slow.data = 1
				slow = slow.next
			fast = fast.next
		return head


class Solution:

	def segregate(self, head):
		zerohead = Node(0)
		onehead = Node(0)
		twohead = Node(0)
		zero = zerohead
		one = onehead
		two = twohead
		temp = head
		while temp:
			if temp.data == 0:
				zero.next = temp
				zero = zero.next
				temp = temp.next
			elif temp.data == 1:
				one.next = temp
				one = one.next
				temp = temp.next
			else:
				two.next = temp
				two = two.next
				temp = temp.next
		if onehead.next != None:
			zero.next = onehead.next
		else:
			zero.next = twohead.next
		one.next = twohead.next
		two.next = None
		head = zerohead.next
		return head


class Solution:

	def segregate(self, head):
		zero = 0
		one = 0
		two = 0
		front = head
		while front is not None:
			if front.data == 0:
				zero += 1
			elif front.data == 1:
				one += 1
			else:
				two += 1
			front = front.next
		front = head
		while zero > 0:
			front.data = 0
			zero -= 1
			front = front.next
		while one > 0:
			front.data = 1
			one -= 1
			front = front.next
		while two > 0:
			front.data = 2
			two -= 1
			front = front.next
		return head


class Solution:

	def segregate(self, head):
		dummy = Node(0)
		dummy.next = head
		prev = head
		curr = head.next
		while curr:
			if curr.data >= prev.data:
				prev = curr
				curr = curr.next
				continue
			tmp = dummy
			while curr.data > tmp.next.data:
				tmp = tmp.next
			prev.next = curr.next
			curr.next = tmp.next
			tmp.next = curr
			curr = prev.next
		return dummy.next


class Solution:

	def segregate(self, head):
		count = [0] * 3
		curr = head
		while curr:
			count[curr.data] += 1
			curr = curr.next
		curr = head
		for i in range(3):
			while count[i] > 0:
				curr.data = i
				count[i] -= 1
				curr = curr.next
		return head


class Solution:

	def segregate(self, head):
		curr = head
		n0 = 0
		n1 = 0
		n2 = 0
		while curr != None:
			if curr.data == 0:
				n0 += 1
			elif curr.data == 1:
				n1 += 1
			else:
				n2 += 1
			curr = curr.next
		temp = head
		curr2 = temp
		for i in range(n0):
			temp.data = 0
			temp = temp.next
		for i in range(n1):
			temp.data = 1
			temp = temp.next
		for i in range(n2):
			temp.data = 2
			temp = temp.next
		return curr2


class Solution:

	def segregate(self, head):
		zero = None
		one = None
		two = None
		zerotail = None
		onetail = None
		twotail = None
		ptr = head
		while ptr:
			if ptr.data == 0:
				if zero is None:
					zero = ptr
					zerotail = ptr
				else:
					zerotail.next = ptr
					zerotail = zerotail.next
			elif ptr.data == 1:
				if one is None:
					one = ptr
					onetail = ptr
				else:
					onetail.next = ptr
					onetail = onetail.next
			elif two is None:
				two = ptr
				twotail = ptr
			else:
				twotail.next = ptr
				twotail = twotail.next
			ptr = ptr.next
		if zerotail:
			zerotail.next = None
		if onetail:
			onetail.next = None
		if twotail:
			twotail.next = None
		if zero:
			sorted = zero
			sortedtail = zerotail
			if one:
				sortedtail.next = one
				sortedtail = onetail
			if two:
				sortedtail.next = two
		elif one:
			sorted = one
			sortedtail = onetail
			if two:
				sortedtail.next = two
		else:
			sorted = two
		return sorted


class Solution(object):

	def segregate(self, head):

		def iterator(fast, slow, value):
			while fast:
				if fast.data == value:
					fast.data = slow.data
					slow.data = value
					slow = slow.next
				fast = fast.next
			return (fast, slow)
		if not head:
			return head
		fast = slow = head
		(fast, slow) = iterator(fast, slow, 0)
		fast = slow
		(fast, slow) = iterator(fast, slow, 1)
		return head


class Solution:

	def segregate(self, head):
		count = [0, 0, 0]
		itr = head
		while itr:
			count[itr.data] += 1
			itr = itr.next
		i = 0
		itr = head
		while itr:
			if count[i] == 0:
				i += 1
			else:
				itr.data = i
				count[i] -= 1
				itr = itr.next
		return head


class Solution:

	def segregate(self, head):
		temp1 = temp2 = head
		while temp1:
			if temp1.data == 0:
				(temp1.data, temp2.data) = (temp2.data, temp1.data)
				temp2 = temp2.next
			temp1 = temp1.next
		temp1 = temp2
		while temp1:
			if temp1.data == 1:
				(temp1.data, temp2.data) = (temp2.data, temp1.data)
				temp2 = temp2.next
			temp1 = temp1.next
		return head


class Solution:

	def segregate(self, head):
		p = head
		a = []
		while p.next != None:
			a.append(p.data)
			p = p.next
		a.append(p.data)
		a.sort()
		p = head
		i = 0
		while p.next != None:
			p.data = a[i]
			i += 1
			p = p.next
		p.data = a[-1]
		return head


class Solution:

	def segregate(self, head):
		cnt_0 = 0
		cnt_1 = 0
		cnt_2 = 0
		(new_head, dummy_head) = (head, head)
		while head:
			if head.data == 0:
				cnt_0 += 1
			elif head.data == 1:
				cnt_1 += 1
			else:
				cnt_2 += 1
			head = head.next
		while cnt_0 > 0:
			new_head.data = 0
			new_head = new_head.next
			cnt_0 -= 1
		while cnt_1 > 0:
			new_head.data = 1
			new_head = new_head.next
			cnt_1 -= 1
		while cnt_2 > 0:
			new_head.data = 2
			new_head = new_head.next
			cnt_2 -= 1
		return dummy_head


class Solution:

	def segregate(self, head):
		array = []
		newnode = head
		result = newnode
		while head:
			array.append(head.data)
			head = head.next
		array = sorted(array)
		for num in array:
			newnode.data = num
			newnode = newnode.next
		return result


class Solution:

	def segregate(self, head):
		(count0, count1, count2) = (0, 0, 0)
		temp = head
		while temp != None:
			if temp.data == 0:
				count0 += 1
			elif temp.data == 1:
				count1 += 1
			else:
				count2 += 1
			temp = temp.next
		temp = head
		while temp != None:
			while temp != None and count0 != 0:
				temp.data = 0
				count0 -= 1
				temp = temp.next
			while temp != None and count1 != 0:
				temp.data = 1
				count1 -= 1
				temp = temp.next
			while temp != None and count2 != 0:
				temp.data = 2
				count2 -= 1
				temp = temp.next
		return head


class Solution:

	def segregate(self, head):
		if head is None:
			return None
		vals = [0, 0, 0]
		temp = head
		while temp is not None:
			vals[temp.data] += 1
			temp = temp.next
		new_head = None
		for i in range(3):
			for j in range(vals[i]):
				if temp:
					temp.next = Node(i)
					temp = temp.next
				else:
					temp = Node(i)
					new_head = temp
		return new_head


class Solution:

	def segregate(self, head):
		(h0, h1, h2) = (None, None, None)
		(t0, t1, t2) = (None, None, None)
		head1 = None
		temp = head
		while temp:
			nex = temp.next
			temp.next = None
			if temp.data == 0:
				if not h0:
					h0 = temp
					t0 = temp
				else:
					t0.next = temp
					t0 = t0.next
			elif temp.data == 1:
				if not h1:
					h1 = temp
					t1 = temp
				else:
					t1.next = temp
					t1 = t1.next
			elif not h2:
				h2 = temp
				t2 = temp
			else:
				t2.next = temp
				t2 = t2.next
			temp = nex
		head1 = h0
		if h0:
			if h1:
				t0.next = h1
			else:
				t0.next = h2
		else:
			head1 = h1
		if h1:
			t1.next = h2
		elif not h0:
			head1 = h2
		return head1


class Solution:

	def segregate(self, head):
		curr = head
		zCount = oCount = tCount = 0
		while curr:
			if curr.data == 0:
				zCount += 1
			elif curr.data == 1:
				oCount += 1
			else:
				tCount += 1
			curr = curr.next
		h = t = head
		while zCount:
			t.data = 0
			zCount -= 1
			t = t.next
		while oCount:
			t.data = 1
			oCount -= 1
			t = t.next
		while tCount:
			t.data = 2
			tCount -= 1
			t = t.next
		return h


class Solution:

	def segregate(self, head):
		zero = Node(0)
		zero_temp = zero
		one = Node(0)
		one_temp = one
		two = Node(0)
		two_temp = two
		temp = head
		while temp is not None:
			data = temp.data
			if data == 0:
				zero_temp.next = temp
				zero_temp = temp
			elif data == 1:
				one_temp.next = temp
				one_temp = temp
			else:
				two_temp.next = temp
				two_temp = temp
			temp = temp.next
		two_temp.next = None
		one_temp.next = two.next
		zero_temp.next = one.next
		head = zero.next
		return head


class Solution:

	def segregate(self, head):
		stack = []
		lemp = head
		while lemp != None:
			stack.append(lemp.data)
			lemp = lemp.next
		stack.sort(reverse=True)
		temp = head
		while stack:
			temp.data = stack.pop()
			temp = temp.next
		return head
		return head.next


class Solution:

	def segregate(self, head):
		fast = head
		l1 = []
		while fast is not None:
			l1.append(fast.data)
			fast = fast.next
		fast = head
		l1.sort()
		for i in l1:
			fast.data = i
			fast = fast.next
		return head


class Solution:

	def segregate(self, head):
		zero = 0
		one = 0
		two = 0
		new_head = head
		ret = head
		temp = head
		while temp:
			if temp.data == 0:
				zero += 1
			elif temp.data == 1:
				one += 1
			elif temp.data == 2:
				two += 1
			temp = temp.next
		while zero != 0:
			new_head.data = 0
			new_head = new_head.next
			zero -= 1
		while one != 0:
			new_head.data = 1
			new_head = new_head.next
			one -= 1
		while two != 0:
			new_head.data = 2
			new_head = new_head.next
			two -= 1
		return head


class Solution:

	def segregate(self, head):
		current = head
		counts = [0, 0, 0]
		while current:
			counts[current.data] += 1
			current = current.next
		prev = None
		for i in range(len(counts)):
			for m in range(counts[i]):
				new_node = Node(i)
				if prev:
					prev.next = new_node
				else:
					new_head = new_node
				prev = new_node
		return new_head


class Solution:

	def segregate(self, head):
		if not head or not head.next:
			return head
		curr = head
		(zerocount, onecount, twocount) = (0, 0, 0)
		while curr:
			if curr.data == 0:
				zerocount += 1
			elif curr.data == 1:
				onecount += 1
			elif curr.data == 2:
				twocount += 1
			else:
				print('invalid input')
			curr = curr.next
		curr = head
		for i in range(zerocount):
			curr.data = 0
			curr = curr.next
		for i in range(onecount):
			curr.data = 1
			curr = curr.next
		for i in range(twocount):
			curr.data = 2
			curr = curr.next
		return head


class Solution:

	def segregate(self, head):
		zero = Node(-2)
		one = Node(-2)
		two = Node(-2)
		(zl, ol, tl) = (zero, one, two)
		temp = head
		while temp:
			if temp.data == 0:
				zero.next = temp
				zero = zero.next
			elif temp.data == 1:
				one.next = temp
				one = one.next
			else:
				two.next = temp
				two = two.next
			temp = temp.next
		zero.next = ol.next
		if ol.next is None:
			zero.next = tl.next
		one.next = tl.next
		two.next = None
		return zl.next


class Solution:

	def segregate(self, head):
		if head == None:
			return head
		count0 = 0
		count1 = 0
		count2 = 0
		curr = head
		while curr:
			val = curr.data
			if val == 0:
				count0 += 1
			elif val == 1:
				count1 += 1
			elif val == 2:
				count2 += 1
			curr = curr.next
		curr = head
		while curr != None:
			val = curr.data
			if count0 != 0:
				curr.data = 0
				count0 -= 1
			elif count1 != 0:
				curr.data = 1
				count1 -= 1
			elif count2 != 0:
				curr.data = 2
				count2 -= 1
			curr = curr.next
		return head


class Solution:

	def segregate(self, head):
		s = []
		c = 0
		while head:
			s.append(head.data)
			c += 1
			head = head.next
		s.sort()
		x = Node(0)
		dummy = x
		t = 0
		while t != c:
			dummy.next = Node(s[t])
			t += 1
			dummy = dummy.next
		return x.next


class Solution:

	def segregate(self, head):
		zero = 0
		one = 0
		two = 0
		curr = head
		while curr:
			if curr.data == 0:
				zero += 1
			elif curr.data == 1:
				one += 1
			else:
				two += 1
			curr = curr.next
		new_head = Node(0)
		temp = new_head
		while zero > 0:
			temp.next = Node(0)
			temp = temp.next
			zero -= 1
		while one > 0:
			temp.next = Node(1)
			temp = temp.next
			one -= 1
		while two > 0:
			temp.next = Node(2)
			temp = temp.next
			two -= 1
		return new_head.next


class Solution:

	def segregate(self, head):
		count = [0, 0, 0]
		ptr = head
		while ptr != None:
			count[ptr.data] += 1
			ptr = ptr.next
		i = 0
		ptr = head
		while ptr != None:
			if count[i] == 0:
				i += 1
			else:
				ptr.data = i
				count[i] -= 1
				ptr = ptr.next
		return head


class Solution:

	def segregate(self, head):
		(cnt0, cnt1, cnt2) = (0, 0, 0)
		newHead = head
		dummyHead = head
		while head:
			if head.data == 0:
				cnt0 += 1
			elif head.data == 1:
				cnt1 += 1
			else:
				cnt2 += 1
			head = head.next
		while cnt0 > 0:
			newHead.data = 0
			newHead = newHead.next
			cnt0 -= 1
		while cnt1 > 0:
			newHead.data = 1
			newHead = newHead.next
			cnt1 -= 1
		while cnt2 > 0:
			newHead.data = 2
			newHead = newHead.next
			cnt2 -= 1
		return dummyHead


class Solution:

	def segregate(self, head):
		arr = []
		cur = head
		while cur:
			arr.append(cur.data)
			cur = cur.next
		arr.sort()
		n = Node(0)
		h = n
		for i in arr:
			k = Node(i)
			n.next = k
			n = n.next
		return h.next


class Solution:

	def segregate(self, head):
		lst = []
		while head:
			lst.append(head.data)
			head = head.next
		lst.sort()
		nn = Node(0)
		current = nn
		for i in lst:
			current.next = Node(i)
			current = current.next
		return nn.next


class Solution:

	def segregate(self, head):
		zeros = zh = Node(0)
		ones = oh = Node(0)
		twos = th = Node(0)
		while head is not None:
			if head.data == 0:
				zeros.next = head
				zeros = head
			elif head.data == 1:
				ones.next = head
				ones = head
			else:
				twos.next = head
				twos = head
			head = head.next
		twos.next = None
		ones.next = th.next
		zeros.next = oh.next
		return zh.next


class Solution:

	def segregate(self, head):
		(zero, one, two) = (Node(-1), Node(-1), Node(-1))
		(curZero, curOne, curTwo) = (zero, one, two)
		while head:
			if head.data == 0:
				curZero.next = head
				curZero = curZero.next
			elif head.data == 1:
				curOne.next = head
				curOne = curOne.next
			else:
				curTwo.next = head
				curTwo = curTwo.next
			head = head.next
		curTwo.next = None
		curOne.next = two.next
		curZero.next = one.next
		return zero.next


class Solution:

	def segregate(self, head):
		l = []
		temp = head
		while temp:
			l.append(temp.data)
			temp = temp.next
		l = sorted(l)
		temp = head
		for i in l:
			temp.data = i
			temp = temp.next
		return head


class Solution:

	def segregate(self, head):
		zeroCount = 0
		oneCount = 0
		twoCount = 0
		temp = head
		while temp:
			if temp.data == 0:
				zeroCount += 1
			elif temp.data == 1:
				oneCount += 1
			elif temp.data == 2:
				twoCount += 1
			temp = temp.next
		temp = head
		while zeroCount > 0:
			temp.data = 0
			zeroCount -= 1
			temp = temp.next
		while oneCount > 0:
			temp.data = 1
			oneCount -= 1
			temp = temp.next
		while twoCount > 0:
			temp.data = 2
			twoCount -= 1
			temp = temp.next
		return head


class Solution:

	def segregate(self, head):
		result = []
		t2 = head
		while t2:
			result.append(t2.data)
			t2 = t2.next
		result.sort()
		newhead = head
		if len(result) == 0:
			return head
		elif len(result) == 1:
			e = Node(result[0])
			e.next = None
			head = e
		else:
			e = Node(result[0])
			e.next = None
			head = e
			t1 = head
			for i in range(1, len(result)):
				while t1.next:
					t1 = t1.next
				e = Node(result[i])
				e.next = None
				t1.next = e
		return head


class Solution:

	def segregate(self, head):
		zerohead = Node(-1)
		zerotail = zerohead
		onehead = Node(-1)
		onetail = onehead
		twohead = Node(-1)
		twotail = twohead
		curr = head
		while curr:
			if curr.data == 0:
				zerotail.next = curr
				zerotail = zerotail.next
			elif curr.data == 1:
				onetail.next = curr
				onetail = onetail.next
			elif curr.data == 2:
				twotail.next = curr
				twotail = twotail.next
			curr = curr.next
		if onehead.next:
			zerotail.next = onehead.next
		else:
			zerotail.next = twohead.next
		onetail.next = twohead.next
		twotail.next = None
		return zerohead.next


class Solution:

	def segregate(self, head):
		zero_count = 0
		ones_count = 0
		twos_count = 0
		current = head
		dummy = Node(-1)
		temp = dummy
		while current:
			if current.data == 0:
				zero_count += 1
				current = current.next
			elif current.data == 1:
				ones_count += 1
				current = current.next
			else:
				twos_count += 1
				current = current.next
		for _ in range(zero_count):
			temp.next = Node(0)
			temp = temp.next
		for _ in range(ones_count):
			temp.next = Node(1)
			temp = temp.next
		for _ in range(twos_count):
			temp.next = Node(2)
			temp = temp.next
		return dummy.next


class Solution:

	def segregate(self, head):
		l = []
		cur = head
		while cur:
			l.append(cur.data)
			cur = cur.next
		l.sort()
		p = []
		for i in l:
			p.append(Node(i))
		p.append(None)
		head = cur = p[0]
		for i in range(1, len(p)):
			cur.next = p[i]
			cur = cur.next
		return head


class Solution:

	def segregate(self, head):
		curr = head
		count0 = 0
		count1 = 0
		count2 = 0
		count = 0
		while curr != None:
			if curr.data == 0:
				count0 += 1
			elif curr.data == 1:
				count1 += 1
			else:
				count2 += 1
			curr = curr.next
		curr1 = head
		while count0 != 0:
			curr1.data = 0
			curr1 = curr1.next
			count0 -= 1
		while count1 != 0:
			curr1.data = 1
			curr1 = curr1.next
			count1 -= 1
		while count2 != 0:
			curr1.data = 2
			curr1 = curr1.next
			count2 -= 1
		return head


class Solution:

	def segregate(self, head):
		curr = head
		nums = []
		while curr:
			nums.append(curr.data)
			curr = curr.next
		l = 0
		m = 0
		h = len(nums) - 1
		if len(nums) == 1:
			return nums
		while m <= h:
			if nums[m] == 1:
				m += 1
			elif nums[m] == 0:
				(nums[l], nums[m]) = (nums[m], nums[l])
				m += 1
				l += 1
			else:
				(nums[h], nums[m]) = (nums[m], nums[h])
				h -= 1
		dummy = Node(-1)
		res = dummy
		for i in nums:
			res.next = Node(i)
			res = res.next
		return dummy.next


class Solution:

	def segregate(self, head):
		d = [0, 0, 0]
		curr = head
		while curr:
			d[curr.data] += 1
			curr = curr.next
		temp = head
		i = 0
		while temp != None:
			if d[i] == 0:
				i = i + 1
			else:
				temp.data = i
				d[i] = d[i] - 1
				temp = temp.next
		return head


class Solution:

	def segregate(self, head):
		c1 = 0
		c2 = 0
		c3 = 0
		temp = head
		while temp != None:
			if temp.data == 0:
				c1 += 1
			elif temp.data == 1:
				c2 += 1
			else:
				c3 += 1
			temp = temp.next
		temp = head
		while temp != None:
			if c1 != 0:
				temp.data = 0
				c1 -= 1
				temp = temp.next
				continue
			if c2 != 0:
				temp.data = 1
				c2 -= 1
				temp = temp.next
				continue
			if c3 != 0:
				temp.data = 2
				c3 -= 1
				temp = temp.next
		return head


class Solution:

	def segregate(self, head):
		if head == None:
			return head
		zero = 0
		one = 0
		two = 0
		cur = head
		while cur != None:
			if cur.data == 0:
				zero += 1
				cur = cur.next
			elif cur.data == 1:
				one += 1
				cur = cur.next
			else:
				two += 1
				cur = cur.next
		temp = head
		for i in range(zero):
			temp.data = 0
			temp = temp.next
		for i in range(one):
			temp.data = 1
			temp = temp.next
		for i in range(two):
			temp.data = 2
			temp = temp.next
		return head


class Solution:

	def segregate(self, head):
		d = []
		temp = head
		while temp:
			d.append(temp.data)
			temp = temp.next
		d.sort()
		curr = head
		for i in d:
			curr.data = i
			curr = curr.next
		return head


class Solution:

	def segregate(self, head):
		zero = one = two = sort = head
		while zero != None:
			if zero.data == 0:
				(zero.data, sort.data) = (sort.data, zero.data)
				sort = sort.next
			zero = zero.next
		one = sort
		while one != None:
			if one.data == 1:
				(one.data, sort.data) = (sort.data, one.data)
				sort = sort.next
			one = one.next
		two = one
		while two != None:
			if two.data == 2:
				(two.data, sort.data) = (sort.data, two.data)
				sort = sort.next
			two = two.next
		return head


class Solution:

	def segregate(self, head):
		c = [0, 0, 0]
		t = head
		while t != None:
			c[t.data] += 1
			t = t.next
		i = 0
		t = head
		while t != None:
			if c[i] == 0:
				i += 1
			else:
				t.data = i
				c[i] -= 1
				t = t.next
		return head


class Solution:

	def segregate(self, head):
		zeroD = Node(0)
		oneD = Node(1)
		twoD = Node(2)
		zero = zeroD
		one = oneD
		two = twoD
		curr_node = head
		while curr_node:
			if curr_node.data == 0:
				zero.next = curr_node
				zero = zero.next
			elif curr_node.data == 1:
				one.next = curr_node
				one = one.next
			else:
				two.next = curr_node
				two = two.next
			curr_node = curr_node.next
		if oneD.next:
			zero.next = oneD.next
		else:
			zero.next = twoD.next
		one.next = twoD.next
		two.next = None
		return zeroD.next


class Solution:

	def segregate(self, head):
		curr = head
		zero = 0
		one = 0
		two = 0
		while curr:
			if curr.data == 0:
				zero += 1
			elif curr.data == 1:
				one += 1
			elif curr.data == 2:
				two += 1
			curr = curr.next
		curr = head
		while curr:
			if zero:
				curr.data = 0
				zero -= 1
			elif one:
				curr.data = 1
				one -= 1
			elif two:
				curr.data = 2
			curr = curr.next
		return head


class Solution:

	def segregate(self, head):
		d = {0: 0, 1: 0, 2: 0}
		h = head
		while h:
			d[h.data] += 1
			h = h.next
		h = head
		c = 0
		while h:
			while d[c] == 0:
				c = min(c + 1, 2)
			h.data = c
			d[c] -= 1
			h = h.next
		return head


class Solution:

	def segregate(self, head):
		curr = head
		D = []
		while curr != None:
			D.append(curr.data)
			curr = curr.next
		D.sort()
		curr = head
		for i in D:
			curr.data = i
			curr = curr.next
		return head


class Solution:

	def segregate(self, head):
		c = []
		curr = head
		while curr:
			c.append(curr.data)
			curr = curr.next
		d = sorted(c)
		curr = head
		for i in d:
			curr.data = i
			curr = curr.next
		return head


class Solution:

	def segregate(self, head):
		ptr1 = head
		a = []
		while ptr1:
			a.append(ptr1.data)
			ptr1 = ptr1.next
		a = sorted(a)
		n = len(a)
		ptr2 = head
		for i in range(n):
			ptr2.data = a[i]
			ptr2 = ptr2.next
		return head


class Solution:

	def segregate(self, head):
		a = []
		while head != None:
			a.append(head.data)
			head = head.next
		a.sort()
		for i in a:
			print(i, end=' ')


class Solution:

	def segregate(self, head):
		arr = []
		temp = head
		while temp:
			arr.append(temp.data)
			temp = temp.next
		low = 0
		high = len(arr) - 1
		mid = 0
		while mid <= high:
			if arr[mid] == 0:
				(arr[low], arr[mid]) = (arr[mid], arr[low])
				low += 1
				mid += 1
			elif arr[mid] == 2:
				(arr[high], arr[mid]) = (arr[mid], arr[high])
				high -= 1
			else:
				mid += 1
		temp = Node(-1)
		head = temp
		for i in arr:
			t = Node(i)
			temp.next = t
			temp = temp.next
		return head.next


class Solution:

	def segregate(self, head):
		counts = [0, 0, 0]
		cur = head
		while cur:
			counts[cur.data] += 1
			cur = cur.next
		cur = head
		for i in range(3):
			for j in range(counts[i]):
				cur.data = i
				cur = cur.next
		return head


class Solution:

	def segregate(self, head):
		zeroFound = oneFound = twoFound = False
		zeroStart = oneStart = twoStart = None
		zeroCur = oneCur = twoCur = None
		cur = head
		while cur:
			if cur.data == 0:
				if zeroStart:
					zeroCur.next = cur
					zeroCur = cur
				else:
					zeroStart = zeroCur = cur
			elif cur.data == 1:
				if oneStart:
					oneCur.next = cur
					oneCur = cur
				else:
					oneStart = oneCur = cur
			elif twoStart:
				twoCur.next = cur
				twoCur = cur
			else:
				twoStart = twoCur = cur
			cur = cur.next
		if zeroCur:
			zeroCur.next = None
		if oneCur:
			oneCur.next = None
		if twoCur:
			twoCur.next = None
		res = cur = Node(-1)
		if zeroStart:
			cur.next = zeroStart
			cur = zeroCur
		if oneStart:
			cur.next = oneStart
			cur = oneCur
		if twoStart:
			cur.next = twoStart
		return res.next


class Solution:

	def segregate(self, head):
		a = head
		arr = [0, 0, 0]
		while a != None:
			arr[a.data] += 1
			a = a.next
		ptr = Node(-1)
		temp = ptr
		for i in range(arr[0]):
			t = Node(0)
			temp.next = t
			temp = t
		for i in range(arr[1]):
			t = Node(1)
			temp.next = t
			temp = t
		for i in range(arr[2]):
			t = Node(2)
			temp.next = t
			temp = t
		return ptr.next


class Solution:

	def segregate(self, head):
		cnt0 = 0
		cnt1 = 0
		cnt2 = 0
		while head:
			if head.data == 0:
				cnt0 += 1
			elif head.data == 1:
				cnt1 += 1
			else:
				cnt2 += 1
			head = head.next
		if cnt2:
			tail = Node(2)
			cnt2 -= 1
		elif cnt1:
			tail = Node(1)
			cnt1 -= 1
		else:
			tail = Node(0)
			cnt0 -= 1
		while cnt2:
			node = Node(2)
			node.next = tail
			tail = node
			cnt2 -= 1
		while cnt1:
			node = Node(1)
			node.next = tail
			tail = node
			cnt1 -= 1
		while cnt0:
			node = Node(0)
			node.next = tail
			tail = node
			cnt0 -= 1
		return tail


class Solution:

	def segregate(self, head):
		l = []
		s = head
		while s != None:
			l.append(s.data)
			s = s.next
		l.sort(reverse=True)
		head1 = None
		for i in l:
			n = Node(i)
			if head1 == None:
				head1 = n
			else:
				n.next = head1
				head1 = n
		return head1


class Solution:

	def segregate(self, head):
		d = [0, 0, 0]
		while head.next != None:
			d[head.data] += 1
			head = head.next
		d[head.data] += 1
		a = LinkedList()
		for i in range(d[0]):
			a.append(0)
		for i in range(d[1]):
			a.append(1)
		for i in range(d[2]):
			a.append(2)
		return a.head


class Solution:

	def __init__(self):
		self.list = []

	def segregate(self, head):
		self.head = head
		curr = head
		while curr != None:
			self.list.append(curr.data)
			curr = curr.next
		self.list.sort()
		curr = head
		counter = 0
		while curr != None:
			curr.data = self.list[counter]
			curr = curr.next
			counter += 1
		return head


class Solution:

	def segregate(self, head):
		ones = LinkedList()
		zeroes = LinkedList()
		twos = LinkedList()
		while head:
			if head.data == 0:
				zeroes.append(0)
			elif head.data == 1:
				ones.append(1)
			else:
				twos.append(2)
			head = head.next
		if zeroes.head:
			if ones.head:
				zeroes.tail.next = ones.head
				zeroes.tail = ones.tail
			if twos.head:
				zeroes.tail.next = twos.head
				zeroes.tail = twos.tail
			return zeroes.head
		elif ones.head:
			if twos.head:
				ones.tail.next = twos.head
				ones.tail = twos.tail
			return ones.head
		else:
			return twos.head
		return zeroes.head


class Solution:

	def segregate(self, head):
		zeroes = 0
		ones = 0
		twos = 0
		start = head
		while start != None:
			if start.data == 0:
				zeroes += 1
			elif start.data == 1:
				ones += 1
			else:
				twos += 1
			start = start.next
		start = head
		while start != None:
			if zeroes > 0:
				start.data = 0
				zeroes -= 1
			elif ones > 0:
				start.data = 1
				ones -= 1
			else:
				start.data = 2
				twos -= 1
			start = start.next
		return head


class Solution:

	def segregate(self, head):
		temp = head
		l = []
		while temp:
			l.append(temp.data)
			temp = temp.next
		l.sort()
		t = head
		n = 0
		while t:
			t.data = l[n]
			n += 1
			t = t.next
		return head


class Solution:

	def segregate(self, head):
		L = []
		n = head
		while n is not None:
			L.append(n.data)
			n = n.next
		L.sort()
		n = head
		while n is not None:
			n.data = L[0]
			L.pop(0)
			n = n.next
		return head


class Solution:

	def segregate(self, head):
		a = head
		p = []
		while a is not None:
			p.append(a.data)
			a = a.next
		list1 = sorted(p)
		head1 = None
		b = None
		for i in list1:
			m = Node(i)
			if head1 is None:
				head1 = m
				b = head1
			else:
				b.next = m
				b = b.next
		return head1