## Description

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


## Solutions

### 1. Merge Sort (Top-down)

# Top-down (recursion)
# Time complexity: O(nlogn)
# Space complexity: O(logn)
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def sortList(self, head: ListNode) -> ListNode:
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# find mid node
mid = slow.next
slow.next = None

def merge(self, left, right):
dummy = ListNode(0)
# where we need to append the non None list
tail = dummy
while left and right:
if left.val > right.val:
left, right = right, left
tail.next = left
left = left.next
tail = tail.next
if left:
tail.next = left
if right:
tail.next = right
return dummy.next

# 16/16 cases passed (232 ms)
# Your runtime beats 61.56 % of python3 submissions
# Your memory usage beats 15.38 % of python3 submissions (21.9 MB)


### 2. Merge Sort (bottom up)

# Time: O(n)
# Space: O(1)

class Solution:
def sortList(self, head: ListNode) -> ListNode:
size = 1
cur = cur.next
while cur:
size += 1
cur = cur.next

dummy = ListNode(0)
i = 1
while i < size:
cur = dummy.next
tail = dummy
while cur:
l = cur
r = self.split(l, i)
cur = self.split(r, i)
first, second = self.merge(l, r)
tail.next = first
tail = second
i = i << 1
return dummy.next

# Splits the list into two parts, first n element and the rest.
# Returns the head of the rest.
while n > 1 and head:
n -= 1
return rest

def merge(self, left, right):
dummy = ListNode(0)
tail = dummy
while left and right:
if left.val > right.val:
left, right = right, left
tail.next = left
left = left.next
tail = tail.next
tail.next = left if left else right
while tail.next:
tail = tail.next
return dummy.next, tail

# 16/16 cases passed (252 ms)
# Your runtime beats 36.81 % of python3 submissions
# Your memory usage beats 15.38 % of python3 submissions (21.8 MB)