Sort List: Merge Sort on a Linked List

Sort List is LeetCode problem 148. It asks you to sort a linked list in ascending order, ideally in O(n log n) time. The natural choice is merge sort, and it maps beautifully onto linked lists because splitting and merging are both pointer operations with no random access needed.

If you already know how to find the middle of a linked list and how to merge two sorted lists, this problem is just combining those two building blocks inside a recursive framework.

The problem

Given the head of a linked list, return the list after sorting it in ascending order.

Example: [4, 2, 1, 3] becomes [1, 2, 3, 4]. Another example: [-1, 5, 3, 4, 0] becomes [-1, 0, 3, 4, 5].

Follow up: Can you sort the linked list in O(n log n) time and O(1) memory (i.e. constant space)?

The approach: merge sort

Merge sort works by splitting the input in half, recursively sorting each half, and merging the two sorted halves. On arrays you need O(n) extra space for the merge buffer. On linked lists, the merge is done in-place by rearranging pointers, so no extra buffer is needed.

The algorithm has three parts:

1. Find the middle using the slow/fast pointer technique. slow moves one step at a time, fast moves two. When fast reaches the end, slow is at the midpoint.
2. Split the list into two halves by cutting the link after slow.
3. Recursively sort each half, then merge the two sorted halves using the standard two-pointer merge.

The base case is a list with zero or one node, which is already sorted.

Visual walkthrough

Let's trace through [4, 2, 1, 3] step by step. First you find the middle and split, then recurse down to single nodes, then merge back up.

Notice how the recursion bottoms out at single-node lists (which are trivially sorted), and then the merge steps build up the sorted result from the bottom. Each merge uses the same two-pointer technique as Merge Two Sorted Lists.

The code

Here is the Python solution:

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

def sort_list(head):
    if not head or not head.next:
        return head

    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = sort_list(head)
    right = sort_list(mid)

    return merge(left, right)

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

Key details to notice:

• fast = head.next instead of fast = head. This ensures that for a two-node list, slow stays at the first node so you split into [first] and [second] rather than getting stuck in infinite recursion.
• slow.next = None severs the link between the two halves. Without this, the left half would still point into the right half.
• The merge function is identical to the solution for Merge Two Sorted Lists. It uses a dummy head node and two pointers, picking the smaller value at each step.
• l1.val <= l2.val uses <= to maintain stability (equal values from the left half come first).

Complexity analysis

The follow-up asks for O(1) space. The recursive version uses O(log n) space due to the call stack. A bottom-up iterative merge sort can achieve true O(1) space by merging sublists of increasing size (1, 2, 4, 8, ...) without recursion. The recursive version shown here is the one you will typically need in interviews.

The building blocks

This problem composes two reusable building blocks that appear in many linked list problems.

Slow/fast pointer to find the middle

You set up two pointers at the head. slow advances one node per step, fast advances two. When fast reaches the end (or its next is null), slow is at the middle. This is the same technique used in:

• Linked List Cycle (LeetCode 141) to detect cycles
• Reorder List (LeetCode 143) to find the midpoint before reversing the second half
• Palindrome Linked List (LeetCode 234) to split and compare halves

Merge two sorted lists

Given two sorted linked lists, merge them into one by comparing heads and picking the smaller value. This is the complete solution to Merge Two Sorted Lists (LeetCode 21), and it also forms the core of:

• Merge K Sorted Lists (LeetCode 23) using divide-and-conquer or a heap
• Any divide-and-conquer algorithm on linked lists

Once these two building blocks are automatic, the sort list solution is just the framework that connects them.

Edge cases to watch for

• Empty list. head is None. The base case returns None immediately.
• Single node. head.next is None. Already sorted. The base case handles this.
• Two nodes. [2, 1]. slow stays at node 0 (since fast = head.next and fast.next is None). Split into [2] and [1]. Merge produces [1, 2].
• Already sorted. [1, 2, 3, 4]. The algorithm still splits and merges, but each merge step just walks through in order. No extra cost beyond the O(n log n) comparisons.
• All identical values. [3, 3, 3]. The <= in the merge function handles this cleanly. The list comes back unchanged.

From understanding to recall

Merge sort on a linked list is a pattern that combines two well-known building blocks. Once you see it, the logic feels natural. But reproducing it under pressure requires remembering specific details: where to initialize fast, where to cut the list, and the dummy-head merge pattern.

Reading the solution once is not enough. The gap between "I understand this" and "I can write this from scratch" is where practice matters. Spaced repetition drills lock in those details so that when you see a sorting or linked list problem, the pieces snap together automatically.

Related posts

• Merge Two Sorted Lists - The merge building block used in this solution, LeetCode 21
• Linked List Cycle - The slow/fast pointer technique for cycle detection, LeetCode 141

---

Visual Learner? Explore how linked list operations work with our Linked List Interactive Visualization.