148. Sort List
On This Page
- 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
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