 # 148. Sort List

Updated: 2023-09-01

LeetCode problem

## Naive Solution

1. Traverse the linked list, adding each node’s value to a Python list
2. sort that list
3. create a new linked list from the sorted values
4. 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:
values = []

while node:
values.append(node.val)
node = node.next

values.sort()

# Create a new linked list from the sorted values
for val in values:
node.val = val
node = node.next



## Solution

Using the Merge Sort algorithm.

1. 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.
2. 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]:

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

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