Sort List — Merge Sort on a Linked List Step by Step

Problem Statement#

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

Constraints:

• The number of nodes in the list is in the range [0, 5 * 10^4]
• -10^5 <= Node.val <= 10^5

Example 1:

Input:  head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]

Example 2:

Input:  head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]

Example 3:

Input:  head = []
Output: []

Why This Problem Matters#

Sort List (LeetCode 148) is a classic medium problem that Amazon, Google, and Facebook use to test whether you can adapt a familiar algorithm (merge sort) to a data structure with no random access. Sorting an array in O(n log n) is trivial — dozens of algorithms work. Sorting a linked list in O(n log n) with O(1) space is genuinely challenging.

Why merge sort specifically? It's the only comparison-based sort that adapts naturally to linked lists:

• Quicksort requires random access to partition efficiently. On a linked list, you'd need O(n) to reach any pivot.
• Heapsort requires a complete binary tree structure.
• Merge sort only needs to split and merge — both operations are natural on linked lists.

The problem has two clean solutions at different levels: top-down (recursive, O(log n) space for the call stack) and bottom-up (iterative, O(1) space). The top-down version is simpler to code; the bottom-up version is the "follow-up" interviewers ask for.

Knowing how to sort a linked list also directly enables understanding of merge K sorted lists (LC 23) and external sorting algorithms used in databases.

The Core Insight#

Merge sort on linked lists:

1. Split: Use fast/slow pointers to find the midpoint. Cut the list there.
2. Recurse: Sort each half recursively.
3. Merge: Merge two sorted lists (LC 21 merge logic).

The key enabler for splitting without knowing the length is the fast/slow pointer trick. When fast reaches the end, slow is at the midpoint.

The merge step is identical to "Merge Two Sorted Lists" — a dummy head and a cursor comparing the front elements of each list.

Visual Dry Run#

Input: 4 -> 2 -> 1 -> 3

Level 0 call: sortList(4->2->1->3)

• Find mid: slow=4,fast=4 → slow=2,fast=1(fast.next=3,fast.next.next=None,stop) → mid=slow=2
• Actually with head.next: slow starts at head=4, fast starts at head.next=2:
  • slow=4, fast=2 → step: slow=2, fast=1 (fast.next=3, fast.next.next=None, stop)
  • mid = slow.next = 1; slow.next = None
  • First half: 4->2, Second half: 1->3

Level 1a: sortList(4->2)

• fast=4.next=2: step → slow=4, fast=None. mid = 4.next = 2; slow.next = None
• First: 4, Second: 2
• sortList(4) = 4, sortList(2) = 2
• merge(4, 2) = 2->4

Level 1b: sortList(1->3)

• merge gives 1->3

Level 0 merge: merge(2->4, 1->3)

Output: 1 -> 2 -> 3 -> 4

Solution (Optimal — Top-Down)#

Python#

def sortList(head):
    # Base case: 0 or 1 node — already sorted
    if not head or not head.next:
        return head
 
    # Step 1: Find midpoint and split
    slow, fast = head, head.next  # fast starts at head.next to get left-midpoint
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    mid = slow.next    # start of second half
    slow.next = None   # cut: sever first half from second half
 
    # Step 2: Recursively sort both halves
    left = sortList(head)
    right = sortList(mid)
 
    # Step 3: Merge the two sorted halves
    dummy = ListNode(0)
    curr = dummy
    while left and right:
        if left.val <= right.val:
            curr.next = left
            left = left.next
        else:
            curr.next = right
            right = right.next
        curr = curr.next
    curr.next = left if left else right
 
    return dummy.next

Time complexity: O(n log n) — log n levels of recursion, O(n) work per level.

Space complexity: O(log n) — call stack depth is log n.

JavaScript#

var sortList = function(head) {
    if (!head || !head.next) return head;
 
    // Find midpoint
    let slow = head, fast = head.next;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
 
    const mid = slow.next;
    slow.next = null;
 
    // Sort both halves
    const left = sortList(head);
    const right = sortList(mid);
 
    // Merge
    const dummy = new ListNode(0);
    let curr = dummy;
    let l = left, r = right;
    while (l !== null && r !== null) {
        if (l.val <= r.val) { curr.next = l; l = l.next; }
        else { curr.next = r; r = r.next; }
        curr = curr.next;
    }
    curr.next = l !== null ? l : r;
 
    return dummy.next;
};

Complexity:

Bottom-Up (O(1) Space) Approach#

The follow-up asks for O(1) space. The bottom-up merge sort merges sublists of doubling size:

def sortList(head):
    if not head or not head.next:
        return head
 
    # Count length
    length = 0
    node = head
    while node:
        length += 1
        node = node.next
 
    dummy = ListNode(0)
    dummy.next = head
 
    size = 1
    while size < length:
        curr = dummy.next
        tail = dummy
 
        while curr:
            left = curr
            right = split(left, size)  # split off size nodes from left, return remainder
            curr = split(right, size)   # split off size nodes from right, return remainder
            merged_tail = merge(left, right)
            tail.next = merged_tail[0]  # head of merged
            tail = merged_tail[1]       # tail of merged
 
        size *= 2
 
    return dummy.next

The bottom-up approach is more complex to implement correctly but achieves O(1) space by avoiding the recursive call stack.

Common Mistakes#

1. Wrong fast pointer initialization. Using slow = fast = head vs slow = head; fast = head.next gives different midpoints for even-length lists. For [1,2,3,4], slow=head, fast=head.next gives mid at node 2 (split: [1,2] and [3,4]). The other gives mid at node 3 (split: [1,2,3] and [4]). Either works, but be consistent and test it.

2. Not cutting at slow.next = None. If you don't sever the first half from the second, the recursive call on head traverses the full list (since slow.next still links to the second half). You'd get infinite recursion (stack overflow) or incorrect results.

3. Modifying head vs using a separate left reference. left = sortList(head) — after the recursive call, head might not be the head of the sorted left half (if the minimum is somewhere else). Always use the returned value, not the original head.

4. Forgetting the base case. if not head or not head.next: return head. Without this, a single-node list would try to find head.next in the fast/slow loop and fail.

5. Off-by-one in merge. After the main while loop in merge, one list might still have nodes. curr.next = left if left else right attaches the remaining nodes. Forgetting this truncates the merged list.

Interview Tips#

1. Justify why merge sort: "Array sorts like heapsort require random access or index arithmetic. Merge sort's split and merge are both natural on linked lists — that's why it's the canonical choice."

2. Draw the recursion tree: Show two levels of splitting and explain that each level does O(n) merging work across all recursive calls.

3. State both space complexities: "Top-down is O(log n) space for the call stack. If O(1) space is required, bottom-up iterative merge sort works."

4. Explain the fast initialization: "I initialize fast at head.next (not head) so that for even-length lists, slow stops at the left-midpoint, giving balanced halves."

5. Separate the merge function: Consider writing a separate mergeTwoLists function for clarity — it shows you recognize this as a reusable component.

Follow-up Questions#

Q: Can you sort a linked list in O(1) space? Yes — bottom-up merge sort iterates over sublist sizes 1, 2, 4, 8, ... merging adjacent pairs at each size. No recursion means no call stack, achieving O(1) extra space.

Q: Why not use quicksort on linked lists? Quicksort's partition requires O(1)-time access to the pivot position, which is O(n) on a linked list. The expected O(n log n) degrades to O(n^2) with bad pivot selection. Merge sort is preferred for linked lists.

Q: What's the time complexity of the bottom-up approach? Also O(n log n) — log n passes, each pass touching every node once. Same asymptotic complexity as top-down.

Q: How does this relate to merging k sorted lists? Merge K Sorted Lists (LC 23) takes k already-sorted lists and merges them. Sort List sorts one unsorted list. The merge step is the same — LC 23 uses a min-heap for efficiency.

Q: Can you sort a doubly linked list more efficiently? Doubly linked lists don't offer asymptotic advantages for sorting, but they allow backward traversal which slightly simplifies certain implementations. Merge sort is still the standard choice.

Key Takeaways#

• Merge sort is the canonical O(n log n) sort for linked lists — the only comparison sort that adapts naturally without random access.
• Split using fast/slow pointers: slow=head, fast=head.next gives a balanced split.
• Always sever the first half with slow.next = None before recursive calls.
• Merge step is identical to "Merge Two Sorted Lists" — reuse that logic.
• Top-down is O(log n) space; bottom-up iterative is O(1) space — know both variants.
• Time is O(n log n): log n recursion levels, O(n) merge work per level.