LeetCode #148 Medium

Sort List

Given the head of a linked list, sort it in ascending order in O(n log n) time and O(1) (or O(log n)) space.

linked-listsortingmerge-sort

02

Intuition

Merge sort is the natural O(n log n) sort for linked lists. Unlike arrays, linked lists cannot be randomly accessed, so quicksort's partition step is awkward. But merge sort's two operations — split in half and merge two sorted halves — are both elegant on linked lists. Split uses the slow-fast pointer trick to find the midpoint. Merge walks two pointers and stitches nodes in order. The recursion depth is O(log n), and each level does O(n) work for splitting and merging, giving O(n log n) total.

How to spot this pattern

When asked to sort a linked list in O(n log n), merge sort is the go-to. The two core operations — find midpoint (slow/fast pointers) and merge two sorted lists — are standard linked list primitives. Quicksort is harder on linked lists because random-access pivoting is expensive. If the problem requires O(1) space, bottom-up merge sort avoids the O(log n) recursion stack.

03

Approach

1

Find the midpoint with slow and fast pointers

Use the classic tortoise-and-hare technique. slow moves one step at a time, fast moves two. When fast reaches the end, slow is at the midpoint. Cut the list in two by setting the node before slow to None. This splits the list into two roughly equal halves.

2

Recursively sort each half

Recurse on the left half and the right half. The base case is a list of length 0 or 1, which is already sorted — return it as is.

3

Merge two sorted halves into one sorted list

Use a dummy node and a tail pointer. Compare the heads of the two sorted halves, append the smaller one to tail, and advance. When one half is exhausted, append the remainder of the other. Return dummy.next. Each merge is O(n) and there are O(log n) levels of recursion, giving O(n log n) total time.

04

Solution

▶1class Solution:
▶2    def sortList(self, head):
▶3        if not head or not head.next:
▶4            return head
▶5        prev = None
▶6        slow = head
▶7        fast = head
▶8        while fast and fast.next:
▶9            prev = slow
▶10            slow = slow.next
▶11            fast = fast.next.next
▶12        prev.next = None
▶13        left = self.sortList(head)
▶14        right = self.sortList(slow)
▶15        return self.merge(left, right)
▶16 
▶17    def merge(self, l1, l2):
▶18        dummy = ListNode(0)
▶19        tail = dummy
▶20        while l1 and l2:
▶21            if l1.val <= l2.val:
▶22                tail.next = l1
▶23                l1 = l1.next
▶24            else:
▶25                tail.next = l2
▶26                l2 = l2.next
▶27            tail = tail.next
▶28        tail.next = l1 if l1 else l2
▶29        return dummy.next

05

Common pitfalls

Not cutting the list at the midpoint before recursing

✗ Wrong

mid = slow
return merge(sortList(head), sortList(mid))

✓ Right

prev.next = None
return merge(sortList(head), sortList(slow))

Without cutting, the left half still points to the right half. The left recursive call processes the entire list, causing infinite recursion.

Finding the wrong midpoint for a two-element list

✗ Wrong

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

✓ Right

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

For a two-element list A -> B, the first version leaves slow at B (the second node), making the left half the entire list and the right half empty — infinite recursion. The second version keeps slow at A, splitting into [A] and [B].

Not handling the base case for a single node

✗ Wrong

if not head:
    return head

✓ Right

if not head or not head.next:
    return head

A single node has no pair to split into. Without the not head.next check, the function tries to find a midpoint of a one-element list, and depending on the splitting logic, may recurse infinitely.

06

Edge cases

Empty list

Base case returns None immediately.

Single node

Base case returns the node as-is. No splitting or merging.

Already sorted list

Merge sort still splits and merges, but the merge step degenerates to appending one half after the other. Same O(n log n) time.

07

Complexity

Time

O(n log n)

Space

O(log n)

O(log n) for the recursion stack. The merge is done in-place by relinking nodes.