← DSA Atlas
Dedicated problem page · #148

Sort List

MediumLinked Lists and Pointer ManipulationMerge sort on a linked listDivide and conquer with slow/fast splitting
Solve on LeetCode ↗
148
MediumLinked Lists and Pointer ManipulationDivide and conquer with slow/fast splittingMerge sort on a linked list

Sort List

Given the head of a singly linked list, sort the nodes into ascending order by value and return the head of the sorted list. You should aim for O(n log n) time.

Open official problem prompt ↗
In plain English

Reorder the existing nodes of a singly linked list so their values are non-decreasing, returning a new head, without copying the values into an array.

Picture it like this

Sorting a shuffled deck by repeatedly cutting it into halves, sorting each half, and then riffle-merging the two ordered piles back into one ordered pile.

Example
Input
head = [4,2,1,3]
Output
[1,2,3,4]
Why
The four node values 4, 2, 1, 3 rearranged in ascending order are 1, 2, 3, 4.
Constraints
The number of nodes is in the range [0, 5 * 10^4]-10^5 <= Node.val <= 10^5Follow up: O(n log n) time and O(1) auxiliary space (excluding recursion stack)
Pattern lesson

See the pattern, then code

Merge sort on a linked list
Recognition clue

You must sort a linked list, not an array, so you cannot random-access an index for quicksort or heapify cheaply. Merge sort only needs sequential access and splitting, which linked lists support in O(1) per pointer move.

↗
Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. Merge sort fits linked lists perfectly: splitting a list at the middle is a slow/fast pointer walk, and merging two sorted lists is just relinking nodes without any extra array. Recurse until sublists have one node, then merge upward.

New words, made simpleKnow these before the algorithm
Merge sort
A divide-and-conquer sort that splits input in half, sorts each half, then merges the sorted halves.
Slow/fast pointers
Two pointers advancing at different speeds so the slow one lands at the midpoint when the fast one reaches the end.
Dummy node
A throwaway head node that removes special-casing for the first element while building a result list.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Copy to array, sort, rebuild

Correct and simple, but uses O(n) extra memory and misses the point of practicing pointer manipulation.

Walk the list into a Python list, call sort(), then overwrite node values in order.

Time O(n log n)Space O(n)
Best choiceTop-down merge sort

Meets the O(n log n) target and only uses stack space proportional to recursion depth; the natural fit for linked lists.

Split at the midpoint with slow/fast pointers, recursively sort each half, and merge by relinking nodes.

Time O(n log n)Space O(log n)
The rule we keep true

Invariant

Every recursive call returns a fully sorted sublist, and the merge step preserves order by always attaching the smaller of the two current heads.

Why this is correct

Reasoning

Merge sort is correct for any sequence: base cases (0 or 1 node) are trivially sorted, and merging two sorted lists yields a sorted list. By induction the whole list becomes sorted. Splitting at the true midpoint keeps recursion depth at log n, giving n log n total merge work.

The algorithm in three movesSay these aloud before coding
1If the list is empty or has one node, it is already sorted; return it

split -> left [4,2], right [1,3]

2Use slow/fast pointers to find the midpoint and cut the list into two halves

sorted left [2,4], sorted right [1,3]

3Recursively sort each half

merge -> [1,2,3,4]

4Merge the two sorted halves by splicing nodes in order

5Return the merged head

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
40
21
12
33
1 · Read[4,2,1,3]
2 · AskWhere is the midpoint?
3 · Update stateslow stops at node 2
4 · ResultCut into left [4,2] and right [1,3]
Key takeaway

The list [4,2,1,3] is split at the midpoint before each half is sorted and merged.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Base case

    A list of length 0 or 1 is already sorted, which also terminates the recursion.

  2. 2
    Lines 5-10Find and cut the midpoint

    Starting fast at head.next guarantees slow lands on the end of the first half so slow.next=None cleanly severs the two halves.

  3. 3
    Lines 11-12Recurse on halves

    Each call returns a sorted sublist to be merged.

  4. 4
    Lines 13-24Merge two sorted lists

    A dummy node lets us append the smaller current node each step, then attach whatever remains of the non-empty list.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty list (head is None)
  • Single node
  • Already sorted or reverse sorted input
  • Duplicate values (use <= to keep the merge stable and avoid dropping ties)
  • Negative values
!

Common beginner mistakes

  • Starting fast at head instead of head.next can fail to split a 2-node list, causing infinite recursion
  • Forgetting slow.next = None leaves the two halves still linked, so the recursion never terminates
  • Comparing with < instead of <= is not wrong for correctness but loses stability
Check your understanding

Why start the fast pointer at head.next rather than head when finding the midpoint?

More in Linked Lists and Pointer Manipulation

#206Reverse Linked ListIterative pointer reversal#141Linked List CycleFast and slow pointers (Floyd's cycle detection)#143Reorder ListFind middle, reverse second half, merge alternately#138Copy List with Random PointerClone with old-to-new node mapping#146LRU CacheHash map plus recency-ordered structure#2Add Two NumbersDigit-by-digit addition with carry