Given a linked list of N nodes, sorted in ascending order based on the absolute values of its data,i.e. negative values are considered as positive ones. Sort the linked list in ascending order according to the actual values, and consider negative numbers as negative and positive numbers as positive.
Example 1:  
Input: 
List: 1, -2, -3, 4, -5
Output: 
List: -5, -3, -2, 1, 4
Explanation: 
Actual sorted order of {1, -2, -3, 4, -5}
is {-5, -3, -2, 1, 4}
 
Example 2:  
Input: 
List: 5, -10
Output: 
List: -10, 5
Explanation:
Actual sorted order of {5, -10}
is {-10, 5}
 
Your Task:
You don't need to read or print anything. Your Task is to complete the function sortList() which takes the head of the Linked List as input parameter and sort the list in ascending order and return the head pointer of the sorted list.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
Constraints
1 ≤  N  ≤ 10^5
-10^5 ≤  node.data ≤ 10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Node:

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

        self.data = data

        self.next = None



class Solution:

    

    def sortList(self,head):

        pass

Solutions:
class Node:

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

class Solution:

	def sortList(self, head):
		a = head
		while a.next:
			if a.next.data < 0:
				k = a.next
				if a.next.next:
					a.next = a.next.next
				else:
					a.next = None
				k.next = head
				head = k
			else:
				a = a.next
		return head


class Node:

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

class Solution:

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


class Node:

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

class Solution:

	def sortList(self, head):
		temp = head
		while temp.next:
			if temp.next.data < 0:
				cur = temp.next
				temp.next = temp.next.next
				cur.next = head
				head = cur
			else:
				temp = temp.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		p1 = None
		p2 = None
		cur = head
		pos = None
		neg = None
		while cur != None:
			if cur.data >= 0:
				new = Node(cur.data)
				if p1 == None:
					p1 = new
					pos = p1
				else:
					p1.next = new
					p1 = new
			else:
				new = Node(cur.data)
				if p2 == None:
					p2 = new
					neg = new
				else:
					p2.next = new
					p2 = new
			cur = cur.next
		if neg == None:
			return head
		if p1:
			p1 = p1.next
		if p2:
			p2 = p2.next
		temp = neg
		neg = self.reverse(neg)
		if pos != None:
			temp.next = pos
		return neg

	def reverse(self, head):
		cur = head
		prev = None
		while cur != None:
			nex = cur.next
			cur.next = prev
			prev = cur
			cur = nex
		return prev


class Node:

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

class Solution:

	def sortList(self, head):
		if not head or not head.next:
			return head
		curr = head.next
		prev = head
		while curr:
			if curr.data < prev.data:
				prev.next = curr.next
				curr.next = head
				head = curr
				curr = prev
			else:
				prev = curr
			curr = curr.next
		return head


class Node:

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

class Solution:

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


class Node:

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

class Solution:

	def sortList(self, start):
		prev = start
		temp = start.next
		while temp:
			if temp.data > 0:
				prev = temp
				temp = temp.next
			else:
				node = Node(temp.data)
				prev.next = temp.next
				temp = prev.next
				node.next = start
				start = node
		return start


class Node:

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

class Solution:

	def sortList(self, head):
		pos = pos_head = Node(0)
		neg = neg_tail = Node(0)
		while head:
			if head.data >= 0:
				pos.next = head
				pos = head
				head = head.next
			else:
				if neg == neg_tail:
					neg_tail = head
				temp = head.next
				head.next = neg.next
				neg.next = head
				head = temp
		pos.next = None
		neg_tail.next = pos_head.next
		return neg.next


class Node:

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

class Solution:

	def sortList(self, head):

		def reverse(head):
			prev = None
			curr = head
			next = head
			while curr:
				next = curr.next
				curr.next = prev
				prev = curr
				curr = next
			return prev
		dummy1 = Node(0)
		tail1 = dummy1
		dummy2 = Node(0)
		tail2 = dummy2
		trav = head
		while trav:
			if trav.data >= 0:
				tail1.next = trav
				tail1 = tail1.next
			elif trav.data < 0:
				tail2.next = trav
				tail2 = tail2.next
			trav = trav.next
		l1 = dummy1.next
		l2 = dummy2.next
		if l2 == None:
			return l1
		tail2.next = None
		tail1.next = None
		l2 = reverse(l2)
		tail2 = dummy2.next
		tail2.next = l1
		return l2


class Node:

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

class Solution:

	def sortList(self, head):
		phead = None
		tphead = None
		nhead = None
		tnhead = None
		while head != None:
			ans = head
			head = head.next
			ans.next = None
			if ans.data < 0:
				if nhead == None:
					nhead = ans
				else:
					ans.next = nhead
					nhead = ans
			elif tphead == None:
				tphead = ans
				phead = tphead
			else:
				tphead.next = ans
				tphead = tphead.next
		tnhead = nhead
		if tnhead != None:
			while tnhead.next != None:
				tnhead = tnhead.next
			tnhead.next = phead
			return nhead
		else:
			return phead


class Node:

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

class Solution:

	def sortList(self, head):
		neg = pos = None
		pg = None
		ng = None
		while head:
			if head.data < 0:
				if not neg:
					ng = head
				nxt = head.next
				head.next = neg
				neg = head
				head = nxt
			else:
				if not pos:
					pos = head
					pg = head
				else:
					pos.next = head
					pos = pos.next
				head = head.next
		if ng:
			ng.next = pg
		else:
			neg = pg
		if pos:
			pos.next = None
		return neg


class Node:

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

class Solution:

	def sortList(self, head):
		l = []
		while head:
			l.append(head.data)
			head = head.next
		l.sort()
		ll = LinkedList()
		for i in l:
			ll.append(i)
		return ll.head


class Node:

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

class Solution:

	def sortList(self, head):
		temp = head
		ar = []
		while temp != None:
			ar.append(temp.data)
			temp = temp.next
		ar.sort()
		temp = head
		i = 0
		while temp != None:
			temp.data = ar[i]
			temp = temp.next
			i += 1
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		if head == None:
			return
		curr = head
		count = 0
		while curr:
			count += 1
			curr = curr.next
		curr = head
		li = []
		for i in range(count):
			li.append(curr.data)
			curr = curr.next
		li.sort()
		head = None
		tail = None
		for ele in li:
			newnode = Node(ele)
			if head == None:
				head = newnode
				tail = newnode
			else:
				tail.next = newnode
				tail = newnode
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		cntpos = 0
		cntneg = 0
		negbeg = None
		posbeg = None
		negend = None
		posend = None
		x = head
		while x:
			if x.data < 0:
				if cntneg == 0:
					negbeg = x
					cntneg += 1
				if negend:
					negend.next = x
				negend = x
			else:
				if cntpos == 0:
					posbeg = x
					cntpos += 1
				if posend:
					posend.next = x
				posend = x
			x = x.next
		p = negbeg
		if p:
			q = p.next
		while p and p != negend:
			t = q.next
			q.next = p
			p = q
			q = t
		negend = negbeg
		negbeg = p
		if negbeg != None:
			head = negbeg
		else:
			head = posbeg
		if negend != None:
			negend.next = posbeg
		if posend != None:
			posend.next = None
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		prev = head
		cur = head.next
		while cur != None:
			if prev.data > cur.data:
				prev.next = cur.next
				cur.next = head
				head = cur
				cur = prev
			else:
				prev = cur
			cur = cur.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		h = []
		j = []
		k = []
		t = head
		temp2 = head
		while t:
			if t.data > 0:
				h.append(t.data)
			else:
				j.append(t.data)
			t = t.next
		k = j[::-1] + h
		for i in k:
			temp2.data = i
			temp2 = temp2.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		neg = []
		pos = []
		res = []
		temp1 = head
		temp2 = head
		while temp1:
			if temp1.data > 0:
				pos.append(temp1.data)
			else:
				neg.append(temp1.data)
			temp1 = temp1.next
		res = neg[::-1] + pos
		for i in res:
			temp2.data = i
			temp2 = temp2.next
		return head
		pass


class Node:

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

class Solution:

	def sortList(self, head):
		prev = head
		curr = head.next
		while curr != None:
			if curr.data < 0:
				while curr and curr.data < 0:
					prev.next = curr.next
					curr.next = head
					head = curr
					curr = prev.next
			else:
				curr = curr.next
				prev = prev.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		u = []
		while head != None:
			u.append(head.data)
			head = head.next
		u = sorted(u)
		head = Node(u[0])
		t = head
		for i in range(1, len(u)):
			r = Node(u[i])
			head.next = r
			head = head.next
		return t


class Node:

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

class Solution:

	def sortList(self, head):

		def rev(head):
			prev = None
			cur = head
			while cur:
				nxt = cur.next
				cur.next = prev
				prev = cur
				cur = nxt
			return prev
		ptr = head
		(e, o) = (Node(-1), Node(-1))
		(ep, op) = (e, o)
		while ptr:
			if ptr.data < 0:
				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
		o = rev(o.next)
		ptr = o
		if not ptr:
			return e.next
		while ptr.next:
			ptr = ptr.next
		ptr.next = e.next
		return o


class Node:

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

class Solution:

	def sortList(self, head):
		li = []
		cur = head
		while cur:
			li.append(cur.data)
			cur = cur.next
		li.sort()
		ind = 0
		cur1 = head
		while cur1:
			cur1.data = li[ind]
			cur1 = cur1.next
			ind += 1
		return head


class Solution:

	def sortList(self, head):
		d = []
		e = []
		t = head
		while t:
			if t.data < 0:
				d.append(t.data)
			else:
				e.append(t.data)
			t = t.next
		d.reverse()
		d += e
		t = head
		for i in d:
			t.data = i
			t = t.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		positive = []
		negative = []
		while head:
			if head.data < 0:
				negative.append(head)
			else:
				positive.append(head)
			head = head.next
		negative.reverse()
		negative += positive
		start = negative[0]
		head = start
		for item in negative[1:]:
			head.next = item
			head = item
		head.next = None
		return start
		pass


class Node:

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

class Solution:

	def sortList(self, head):
		neg = -1
		neg_last = neg
		pos = Node(1)
		pos_last = pos
		c = 0
		while head:
			if head.data < 0:
				temp = head
				head = head.next
				temp.next = neg
				neg = temp
				if c == 0:
					neg_last = temp
					c += 1
			else:
				temp = head
				head = head.next
				temp.next = None
				pos_last.next = temp
				pos_last = pos_last.next
		if c != 0:
			neg_last.next = pos.next
			return neg
		else:
			return pos.next


class Node:

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

class Solution:

	def sortList(self, head):
		s = []
		temp = head
		while temp != None:
			s.append(temp.data)
			temp = temp.next
		s = sorted(s)
		temp = head
		c = 0
		while temp != None:
			temp.data = s[c]
			c += 1
			temp = temp.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		a = head
		v = []
		dummy = Node(0)
		b = dummy
		while a:
			v.append(a.data)
			a = a.next
		v.sort()
		for i in v:
			b.next = Node(i)
			b = b.next
		return dummy.next


class Node:

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

class Solution:

	def sortList(self, head):
		temp = head
		while temp.next:
			if temp.next.data < 0:
				k = temp.next
				if temp.next.next:
					temp.next = temp.next.next
				else:
					temp.next = None
				k.next = head
				head = k
			else:
				temp = temp.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		new = Node(0)
		curr = head
		x = []
		tmp = new
		while curr:
			x.append(curr.data)
			curr = curr.next
		for i in sorted(x):
			tmp.next = Node(i)
			tmp = tmp.next
		return new.next


class Node:

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

class Solution:

	def sortList(self, head):
		l = []
		t = head
		while t != None:
			l.append(t.data)
			t = t.next
		l = sorted(l)
		t = head
		for i in range(len(l)):
			t.data = l[i]
			t = t.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		l = []
		h = head
		while h:
			l.append(h.data)
			h = h.next
		l.sort()
		a = b = Node(-1)
		for i in l:
			a.next = Node(i)
			a = a.next
		return b.next


class Node:

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

class Solution:

	def sortList(self, head):
		last_neg = None
		prev = None
		cur = head
		while cur:
			if cur.data < 0:
				last_neg = cur
				break
			prev = cur
			cur = cur.next
		if last_neg is None:
			return head
		negative_tail = last_neg
		cur = last_neg.next
		prev1 = last_neg
		while cur:
			if cur.data < 0:
				temp = cur.next
				prev1.next = temp
				if prev:
					temp2 = prev.next
					prev.next = cur
					cur.next = temp2
				else:
					cur.next = last_neg
					last_neg = cur
					head = cur
				cur = prev1.next
				continue
			prev1 = cur
			cur = cur.next
		if head.data < 0:
			return head
		negative_head = prev.next
		positive_head = head
		head = negative_head
		temp2 = negative_tail.next
		negative_tail.next = positive_head
		prev.next = temp2
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		curr = head
		while curr != None and curr.next != None:
			if curr.next.data >= 0:
				curr = curr.next
			else:
				oldH = head
				pre = curr
				move = curr.next
				pre.next = curr.next.next
				head = move
				head.next = oldH
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		z = []
		while head is not None:
			z.append(head.data)
			head = head.next
		z.sort()
		z.append('x')
		head = None
		taily = None
		for ele in z:
			newnode = Node(ele)
			if ele != 'x':
				if head is None:
					head = newnode
					taily = newnode
				else:
					taily.next = newnode
					taily = newnode
		return head


class Node:

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

class Solution:

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


class Node:

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

class Solution:

	def sortList(self, head):
		l = []
		if head is None:
			return
		else:
			n = head
			while n is not None:
				l.append(n.data)
				n = n.next
		for i in sorted(l):
			print(i, end=' ')


class Node:

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

class Solution:

	def sortList(self, head):
		pre = head
		curr = head.next
		while curr:
			if pre.data <= curr.data:
				pre = pre.next
				curr = curr.next
			else:
				pre.next = curr.next
				curr.next = head
				head = curr
				curr = pre.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		values = list()
		while head:
			values.append(head.data)
			head = head.next
		values.sort()
		ans = Node(0)
		curr = ans
		for i in values:
			curr.next = Node(i)
			curr = curr.next
		return ans.next
		pass


class Node:

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

class Solution:

	def sortList(self, head):
		if not head:
			return
		p1 = head
		head2 = Node(p1.data)
		p1 = p1.next
		start = head2
		end = head2
		while p1:
			if p1.data < 0:
				val = Node(p1.data)
				val.next = start
				start = val
			else:
				val = Node(p1.data)
				end.next = val
				end = val
			p1 = p1.next
		return start


class Node:

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

class Solution:

	def sortList(self, start):
		if start.next is None:
			return start
		prev = start
		curr = start.next
		while curr:
			if curr.data < 0:
				prev.next = curr.next
				curr.next = start
				start = curr
				curr = prev.next
			else:
				prev = curr
				curr = curr.next
		return start


class Node:

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

class Solution:

	def sortList(self, head):
		pointer = head
		lista = []
		while pointer:
			lista.append(pointer.data)
			pointer = pointer.next
		lista.sort()
		pointer = head
		for y in lista:
			pointer.data = y
			pointer = pointer.next
		return head


class Node:

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

class Solution:

	def sortList(self, head):
		arr = []
		while head:
			arr += [head.data]
			head = head.next
		arr.sort()
		nl = Node(0)
		kk = nl
		for i in arr:
			nl.next = Node(i)
			nl = nl.next
		return kk.next


class Node:

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

class Solution:

	def split(self, head):
		positiveHead = positiveTail = Node(None)
		negativeHead = negativeTail = Node(None)
		ptr = head
		while ptr:
			if ptr.data < 0:
				negativeTail.next = ptr
				negativeTail = ptr
			else:
				positiveTail.next = ptr
				positiveTail = ptr
			ptr = ptr.next
		positiveTail.next = None
		negativeTail.next = None
		return (positiveHead.next, negativeHead.next)

	def reverse(self, head):
		prevNode = currNode = None
		nextNode = head
		while nextNode:
			prevNode = currNode
			currNode = nextNode
			nextNode = nextNode.next
			currNode.next = prevNode
		return currNode

	def sortList(self, head):
		(pos, neg) = self.split(head)
		negRev = self.reverse(neg)
		if neg:
			neg.next = pos
			return negRev
		return pos


class Node:

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

class Solution:

	def sortList(self, head):
		a = []
		while head:
			a.append(head.data)
			head = head.next
		a.sort()
		s = None
		sh = None
		for i in a:
			if not s:
				s = Node(i)
				sh = s
			else:
				s.next = Node(i)
				s = s.next
		return sh


class Node:

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

class Solution:

	def sortList(self, head):
		li = []
		ti = []
		while head:
			if head.data >= 0:
				li.append(head.data)
			else:
				ti.append(head.data)
			head = head.next
		b = a = Node(0)
		for i in range(len(ti) - 1, -1, -1):
			a.next = Node(ti[i])
			a = a.next
		for i in range(len(li)):
			a.next = Node(li[i])
			a = a.next
		return b.next


class Node:

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

class Solution:

	def getReversed(self, curr, prev):
		while curr:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		return prev

	def sortList(self, head):
		pass
		list1Head = list1 = Node(0)
		list2Head = list2 = Node(0)
		curr = head
		while curr:
			if curr.data <= 0:
				list2.next = curr
				list2 = list2.next
			else:
				list1.next = curr
				list1 = list1.next
			curr = curr.next
		list1.next = None
		list2.next = None
		list2 = self.getReversed(list2Head.next, list1Head.next)
		return list2


class Node:

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

class Solution:

	def sortList(self, head):
		a = []
		b = head
		while b:
			a.append(b.data)
			b = b.next
		a.sort()
		g = h = Node(a[0])
		for i in range(1, len(a)):
			g.next = Node(a[i])
			g = g.next
		return h


class Node:

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

class Solution:

	def sortList(self, head):
		res = []
		temp = head
		while temp != None:
			res.append(temp.data)
			temp = temp.next
		res.sort()
		res_ll = Node(res[0])
		l3 = res_ll
		for i in range(1, len(res)):
			l3.next = Node(res[i])
			l3 = l3.next
		return res_ll
		pass


class Node:

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

class Solution:

	def sortList(self, head):
		l = []
		while head != None:
			l.append(head.data)
			head = head.next
		l.sort()
		return Node(' '.join(map(str, l)))


class Node:

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

class Solution:

	def reverseList(self, head):
		pre = None
		trav = head
		nhead = head
		while trav:
			ele = trav.next
			trav.next = pre
			nhead = trav
			pre = trav
			trav = ele
		return nhead

	def sortList(self, head):
		pre = None
		pos = None
		nhead = None
		nhead2 = None
		h1 = h2 = head
		while h1:
			if h1.data < 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
			h1 = h1.next
			if pos and pos.next:
				pos.next = None
			if pre and pre.next:
				pre.next = None
		if nhead:
			nhead = self.reverseList(nhead)
			last = nhead
			while last.next:
				last = last.next
			last.next = nhead2
			return nhead
		return nhead2


import collections

class Node:

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

class Solution:

	def sortList(self, head):
		datalist = []
		head1 = head
		i = -1
		while head:
			datalist.append(head.data)
			head = head.next
			i += 1
		datalist.sort(reverse=True)
		values = collections.deque(datalist)
		head = head1
		while head:
			head.data = datalist[i]
			i -= 1
			head = head.next
		return head1


class Node:

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

class Solution:

	def sortList(self, head):
		b = []
		temp = head
		while temp != None:
			b.append(temp.data)
			temp = temp.next
		b.sort()
		temp = head
		for i in b:
			temp.data = i
			temp = temp.next
		return head