148. Sort List
On This Page
Naive Solution
- Traverse the linked list, adding each node’s value to a Python list
- sort that list
- create a new linked list from the sorted values
- return the head of this new list.
This solution would have a time complexity of O(n log n) due to the sort operation and a space complexity of O(n) because of the extra list we’re creating.
class Solution:
def sortList(self, head):
values = []
node = head
while node:
values.append(node.val)
node = node.next
values.sort()
# Create a new linked list from the sorted values
node = head
for val in values:
node.val = val
node = node.next
return head
Solution
Using the Merge Sort algorithm.
- Divide and Conquer: Merge sort uses the divide and conquer strategy, where we continuously split the linked list in half until we have multiple sublists of length 1. A list of length 1 is technically always sorted.
- Merge Sublists: Once we have the sorted sublists, we start merging them together in a manner that the resultant list is also sorted.
The trick to making this solution O(1) space complexity is to modify the existing nodes’ next pointers to generate the sorted list, rather than creating new nodes.
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None # separate left and right halves of linked list
left = self.sortList(head)
right = self.sortList(mid)
def merge(left, right):
if not left or not right:
return left or right
if left.val > right.val: # sort
left, right = right, left
left.next = merge(left.next, right)
return left
res = merge(left, right)
return res