148. Sort List - Explanation

1. Convert To Array

Intuition

Linked lists are notoriously difficult to sort in place due to lack of random access. A straightforward workaround is to extract all node values into an array, sort the array using a built-in sorting algorithm, and then write the sorted values back into the linked list nodes. This leverages efficient array sorting while preserving the original list structure.

Algorithm

Traverse the linked list and collect all node values into an array.
Sort the array using a standard sorting algorithm.
Traverse the linked list again, updating each node's value with the corresponding sorted value from the array.
Return the head of the list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        arr = []
        cur = head

        while cur:
            arr.append(cur.val)
            cur = cur.next

        arr.sort()
        cur = head
        for val in arr:
            cur.val = val
            cur = cur.next

        return head

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Recursive Merge Sort

Intuition

Merge sort is well suited for linked lists because merging two sorted lists can be done efficiently without extra space by rearranging pointers. We recursively split the list in half using the slow and fast pointer technique to find the middle, sort each half, and then merge the two sorted halves together. This divide-and-conquer approach achieves O(n log n) time complexity.

Algorithm

Base case: if the list is empty or has one node, return it as is.
Use slow and fast pointers to find the middle of the list. The slow pointer will end at the node before the midpoint.
Split the list into two halves by setting the next pointer of the middle node to null.
Recursively sort the left half and right half.
Merge the two sorted halves by comparing node values and linking nodes in sorted order.
Return the merged sorted list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        left = head
        right = self.getMid(head)
        tmp = right.next
        right.next = None
        right = tmp

        left = self.sortList(left)
        right = self.sortList(right)
        return self.merge(left, right)

    def getMid(self, head):
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def merge(self, list1, list2):
        tail = dummy = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        if list1:
            tail.next = list1
        if list2:
            tail.next = list2

        return dummy.next

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(\log n)$ for recursion stack.

3. Iterative Merge Sort

Intuition

The recursive merge sort uses O(log n) space for the call stack. To achieve true O(1) extra space, we can implement merge sort iteratively using a bottom-up approach. Instead of recursively splitting the list, we start by treating each node as a sorted sublist of size 1, then merge adjacent pairs into sorted sublists of size 2, then 4, and so on until the entire list is sorted.

Algorithm

Count the total length of the linked list.
Use a dummy node to simplify head management during merges.
Start with a step size of 1 and double it each iteration until it reaches the list length.
For each step size, traverse the list and split off pairs of sublists of that size.
Merge each pair of sublists and attach the merged result to the previous portion of the list.
After all iterations complete, return the sorted list starting from dummy.next.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next

        dummy = ListNode(0)
        dummy.next = head
        step = 1

        while step < length:
            prev, curr = dummy, dummy.next
            while curr:
                left = curr
                right = self.split(left, step)
                curr = self.split(right, step)
                merged = self.merge(left, right)
                prev.next = merged
                while prev.next:
                    prev = prev.next
            step *= 2

        return dummy.next

    def split(self, head, step):
        if not head:
            return None
        for _ in range(step - 1):
            if not head.next:
                break
            head = head.next
        next_part = head.next
        head.next = None
        return next_part

    def merge(self, list1, list2):
        tail = dummy = ListNode(0)
        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        tail.next = list1 or list2
        return dummy.next

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$

Common Pitfalls

Incorrect Mid-Point Calculation for List Splitting

When finding the middle of the linked list, starting fast at head instead of head.next can lead to incorrect splitting, especially for lists with two elements. This causes infinite recursion as the list never gets properly divided.

Forgetting to Disconnect the Two Halves

After finding the middle node, you must set mid.next = null to properly split the list into two separate halves. Failing to disconnect them results in the merge sort operating on overlapping lists, causing incorrect results or infinite loops.

Not Handling Edge Cases for Empty or Single-Node Lists

The base case must return immediately if head is null or head.next is null. Missing this check leads to null pointer exceptions or infinite recursion when the algorithm tries to split a list that cannot be divided further.