Sort a linked list in O(n log n) time using constant space complexity.

Example 1:


Input: 4->2->1->3
Output: 1->2->3->4


Example 2:


Input: -1->5->3->4->0
Output: -1->0->3->4->5

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        

Solutions:
# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def sortList(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         arr = []
         p = head
         while p:
             arr.append(p.val)
             p = p.next
             
         arr.sort()
         p = head
         for el in arr:
             p.val = el
             p = p.next
         
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def sortList(self, head):
         l = []
         traverse, traverse2 = head, head
         while(traverse) != None:
             l.append(traverse.val)
             traverse = traverse.next
         l.sort()
         for num in l:
             traverse2.val = num
             traverse2 = traverse2.next
         return head