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:
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# find mid node
mid = slow.next
slow.next = None
return self.merge(self.sortList(head),self.sortList(mid))
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:
if not head or not head.next:
return head
size = 1
cur = head
cur = cur.next
while cur:
size += 1
cur = cur.next
dummy = ListNode(0)
dummy.next = head
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
def split(self, head, n):
# Splits the list into two parts, first n element and the rest.
# Returns the head of the rest.
while n > 1 and head:
head = head.next
n -= 1
rest = head.next if head else None
if head:
head.next = None
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)