LeetCode 148: Sort List Solution in Python Explained

Problem Statement

In LeetCode 148, you’re given the head of a singly linked list. Your task is to sort it in ascending order and return the head, achieving O(n log n) time complexity and O(1) space complexity (excluding recursion stack space). This builds on LeetCode 147: Insertion Sort List, improving from O(n²) to O(n log n) with merge sort, and differs from cache management like LeetCode 146: LRU Cache.

Constraints

• Number of nodes: 0 <= n <= 5 * 10^4
• Node values: -10^5 <= Node.val <= 10^5

Example

Let’s see some cases:

Copy codeInput: head = [4,2,1,3]
Output: [1,2,3,4]
Explanation: 
<ul>
<li>Original: 4->2->1->3</li>
<li>Sorted: 1->2->3->4</li>
</ul>

Copy codeInput: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: 
<ul>
<li>Original: -1->5->3->4->0</li>
<li>Sorted: -1->0->3->4->5</li>
</ul>

Copy codeInput: head = []
Output: null
Explanation: Empty list, return null.

These examples show we’re sorting the list with merge sort.

Understanding the Problem

How do you solve LeetCode 148: Sort List in Python? Take head = [4,2,1,3]. We need to sort it to 1->2->3->4 in O(n log n) time and O(1) space (excluding recursion). Merge sort splits the list into halves, sorts them, and merges them back. For [-1,5,3,4,0], it becomes -1->0->3->4->5. This improves on LeetCode 147’s insertion sort, and isn’t a traversal like LeetCode 145: Binary Tree Postorder Traversal. We’ll use: 1. Merge Sort with Bottom-Up Approach: O(n log n) time, O(1) space—our best solution. 2. Top-Down Merge Sort: O(n log n) time, O(log n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Merge Sort with Bottom-Up Approach

Explanation

Merge Sort with Bottom-Up Approach iteratively merges sublists of increasing size (1, 2, 4, …) until the entire list is sorted, avoiding recursion. It: 1. Splits the list into pairs of sublists. 2. Merges each pair in sorted order. 3. Repeats with larger sublist sizes.

This is the best solution due to its O(n log n) time complexity, true O(1) space usage (no recursion stack), and iterative nature, making it efficient and space-optimal for the problem’s constraints.

For [4,2,1,3]:

• Size 1: [4,2] and [1,3].
• Merge: 2->4, 1->3.
• Size 2: Merge 2->4 and 1->3 → 1->2->3->4.

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next.

Example 1: head = [4,2,1,3]

Goal: Return [1,2,3,4].

• Step 1: Count length = 4.
• Step 2: Size = 1.
• Split: [4],[2],[1],[3].
• Merge pairs: 4->2 → 2->4, 1->3 → 1->3.
• List: 2->4->1->3.
• Step 3: Size = 2.
• Split: [2,4],[1,3].
• Merge: 2->4 and 1->3 → 1->2->3->4.
• Step 4: Size = 4 (done).
• Finish: Return 1.

Example 2: head = [-1,5,3,4,0]

Goal: Return [-1,0,3,4,5].

• Step 1: Length = 5.
• Step 2: Size = 1.
• Merge: -1->5 → -1->5, 3->4 → 3->4, [0].
• List: -1->5->3->4->0.
• Step 3: Size = 2.
• Merge: -1->5 and 3->4 → -1->3->4->5, [0].
• List: -1->3->4->5->0.
• Step 4: Size = 4.
• Merge: -1->3->4->5 and 0 → -1->0->3->4->5.
• Finish: Return -1.

Example 3: head = []

Goal: Return null.

• Start: Null input, return null.
• Finish: Return null.

How the Code Works (Merge Sort with Bottom-Up) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sortList(head: ListNode) -> ListNode:
    # Line 1: Handle null or single node cases
    if not head or not head.next:
        # If head is None or single (e.g., []), return as is
        return head

    # Line 2: Count list length
    length = 0
    curr = head
    while curr:
        # Count nodes (e.g., 4 for [4,2,1,3])
        length += 1
        curr = curr.next

    # Line 3: Initialize dummy node
    dummy = ListNode(0)
    # Dummy head for sorted list (e.g., 0)
    dummy.next = head
    # Link to original list (e.g., 0->4->...)

    # Line 4: Iterate over sublist sizes
    size = 1
    # Start with size 1 (e.g., 1, 2, 4)
    while size < length:
        # Continue until size covers list (e.g., 1 < 4)

        # Line 5: Process sublists of current size
        curr = dummy.next
        # Start at list head (e.g., 4)
        tail = dummy
        # Tail of merged list (e.g., 0)
        while curr:
            # While nodes remain (e.g., 4->2->...)

            # Line 6: Split first sublist
            left = curr
            # First sublist start (e.g., 4)
            right = self._split(left, size)
            # Split after size (e.g., 2->1->...)
            curr = self._split(right, size) if right else None
            # Next sublist (e.g., 1->3)

            # Line 7: Merge sublists
            merged = self._merge(left, right)
            # Merge (e.g., 2->4)
            tail.next = merged
            # Link to previous (e.g., 0->2->4)
            while tail.next:
                # Move tail to end (e.g., 4)
                tail = tail.next

        # Line 8: Increase sublist size
        size *= 2
        # Double size (e.g., 2, then 4)

    # Line 9: Return sorted list head
    return dummy.next
    # Final sorted list (e.g., 1->2->3->4)

    def _split(self, head: ListNode, size: int) -> ListNode:
        # Helper: Split list after size nodes
        curr = head
        for _ in range(size - 1):
            # Move size-1 steps (e.g., 1 step for size=2)
            if curr:
                curr = curr.next
        if not curr:
            return None
        next_start = curr.next
        # Next sublist start (e.g., 1 for size=2)
        curr.next = None
        # Break link (e.g., 4->2->null)
        return next_start
        # Return next sublist (e.g., 1->3)

    def _merge(self, l1: ListNode, l2: ListNode) -> ListNode:
        # Helper: Merge two sorted lists
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            # While both lists have nodes (e.g., 2->4, 1->3)
            if l1.val < l2.val:
                # Take smaller (e.g., 1 < 2)
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        # Attach remaining
        curr.next = l1 if l1 else l2
        # e.g., 1->2->3->4
        return dummy.next

This detailed breakdown clarifies how the bottom-up merge sort efficiently sorts the list.

Alternative: Top-Down Merge Sort Approach

Explanation

Top-Down Merge Sort recursively splits the list into halves using a slow-fast pointer, sorts each half, and merges them. It’s a practical alternative, also O(n log n) time, but uses O(log n) space for the recursion stack, making it less space-efficient than the bottom-up approach.

For [4,2,1,3]:

• Split: 4->2, 1->3.
• Recurse: 2->4, 1->3.
• Merge: 1->2->3->4.

Step-by-Step Example (Alternative)

For [4,2,1,3]:

• Step 1: Split at 2: 4->2, 1->3.
• Step 2: Sort 4->2 → 2->4, 1->3 → 1->3.
• Step 3: Merge 2->4 and 1->3 → 1->2->3->4.
• Finish: Return 1.

How the Code Works (Top-Down)

Copy codedef sortListTopDown(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    slow = fast = head
    prev = None
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    prev.next = None

    left = sortListTopDown(head)
    right = sortListTopDown(slow)

    def merge(l1, l2):
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 if l1 else l2
        return dummy.next

    return merge(left, right)

Complexity

• Merge Sort with Bottom-Up Approach:
• Time: O(n log n) – merge sort iterations.
• Space: O(1) – constant space.
• Top-Down Merge Sort:
• Time: O(n log n) – recursive merge sort.
• Space: O(log n) – recursion stack.

Efficiency Notes

Merge Sort with Bottom-Up Approach is the best solution with O(n log n) time and O(1) space, meeting the problem’s strict space constraint—Top-Down Merge Sort matches time complexity but uses O(log n) space due to recursion, making it a standard but less space-efficient alternative.

Key Insights

• Merge Sort: Divide and conquer.
• Bottom-Up: Iterative efficiency.
• Top-Down: Recursive simplicity.

Additional Example

For head = [3,1,4,2]:

• Goal: [1,2,3,4].
• Bottom-Up: Merge 1->3, 2->4 → 1->2->3->4.

Edge Cases

• Empty List: [] → null.
• Single Node: [1] → [1].
• Duplicates: [1,1] → [1,1].

Both solutions handle these well.

Final Thoughts

LeetCode 148: Sort List in Python is a sophisticated sorting challenge. The Merge Sort with Bottom-Up Approach excels with its space efficiency and iterative design, while Top-Down Merge Sort offers a recursive alternative. Want more? Try LeetCode 147: Insertion Sort List for insertion sort or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 148 on LeetCode with [4,2,1,3], aiming for [1,2,3,4]—test your skills now!