TL;DR
Merge sort on the list — top-down (O(n log n) time, O(log n) stack) or bottom-up (O(n log n) time, O(1) space).
Approach 1 — Brute force: copy values out, sort, copy back
Ignore the structure: pull every value into a Python list, sort it, then walk the list again overwriting node values in order.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
vals = []
node = head
while node:
vals.append(node.val)
node = node.next
vals.sort()
node = head
for v in vals:
node.val = v
node = node.next
return head
Time O(n log n), space O(n). The time is fine; the O(n) auxiliary array is the problem. The follow-up asks for constant extra space, and copying values out sidesteps the linked-list manipulation the problem is testing.
Approach 2 — Top-down merge sort
Merge sort is the classic O(n log n) sort that never needs random access: it only splits and merges, and both are natural pointer operations on a linked list. It halves the input, sorts each half, and merges the two sorted halves. Find the middle with slow/fast pointers, cut the list there, recurse on each half, then merge.
flowchart TD
A["4, 2, 1, 3"] --> B["4, 2"]
A --> C["1, 3"]
B --> D["4"]
B --> E["2"]
C --> F["1"]
C --> G["3"]
D --> H["2, 4"]
E --> H
F --> I["1, 3"]
G --> I
H --> J["1, 2, 3, 4"]
I --> J
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
# Find the node BEFORE the middle, then cut.
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
left = sortList(head)
right = sortList(mid)
# Merge two sorted lists.
dummy = ListNode()
tail = dummy
while left and right:
if left.val <= right.val:
tail.next = left
left = left.next
else:
tail.next = right
right = right.next
tail = tail.next
tail.next = left if left else right
return dummy.next
Walkthrough on [4, 2, 1, 3]: slow/fast stops with slow on 4 (fast started at head.next, so the cut is balanced), cutting into [4, 2] and [1, 3]. Recursing on [4, 2] cuts it into [4] and [2], which merge to [2, 4]. [1, 3] is cut into [1] and [3], merging to [1, 3]. The final merge compares 2 vs 1 → take 1, 2 vs 3 → take 2, 4 vs 3 → take 3, then appends the leftover 4: [1, 2, 3, 4].
Time O(n log n) — log n levels of splitting, O(n) merge work per level. Space O(log n) for the recursion stack (no arrays).
Approach 3 — Bottom-up merge sort (true O(1) space)
Recursion exists only to discover the run boundaries. Fix the run length explicitly instead (merge runs of length 1, then 2, then 4, and so on) and you get the same merge tree iteratively with no stack. Each pass walks the list once, splitting off two runs of the current length and merging them in place.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def split(head: Optional[ListNode], step: int) -> Optional[ListNode]:
"""Detach the first `step` nodes; return what follows them."""
for _ in range(step - 1):
if not head:
break
head = head.next
if not head:
return None
rest = head.next
head.next = None
return rest
def merge(l1: Optional[ListNode], l2: Optional[ListNode],
prev: ListNode) -> ListNode:
"""Merge two sorted runs after `prev`; return the merged run's tail."""
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
prev.next = l1 if l1 else l2
while prev.next:
prev = prev.next
return prev
def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
n = 0
node = head
while node:
n += 1
node = node.next
dummy = ListNode(0, head)
step = 1
while step < n:
prev, curr = dummy, dummy.next
while curr:
left = curr
right = split(left, step)
curr = split(right, step)
prev = merge(left, right, prev)
step *= 2
return dummy.next
Walkthrough on [4, 2, 1, 3]: pass with step = 1 merges the runs [4]+[2] → [2, 4] and [1]+[3] → [1, 3], leaving [2, 4, 1, 3]. Pass with step = 2 splits off [2, 4] and [1, 3] and merges them → [1, 2, 3, 4]. step becomes 4 ≥ n, done.
Time O(n log n) — log n passes, each O(n). Space O(1): a dummy node and a few pointers.
Common pitfalls
- Slow/fast starting points. Starting
fast = head (instead of head.next) makes slow land on the middle for even lengths, and a 2-node list splits into [] + [both] — infinite recursion. Start fast one ahead, or track the node before slow.
- Forgetting to cut. After finding the middle you must set
slow.next = None; otherwise both recursive calls see the whole list.
- Bottom-up tail hookup. After merging a run pair, the merged tail must be advanced to the true end (
while prev.next) before splicing the next pair, or later runs get orphaned.
- Reaching for quicksort. Quicksort on a list is doable but degrades to O(n^2) on sorted/duplicate-heavy input (a classic LeetCode test case); merge sort is the intended tool.
Pattern takeaway
When a problem asks you to reorder a linked list wholesale, ask which classic algorithm works with only sequential access. Merge sort is the answer, built from two reusable primitives: slow/fast middle-finding and the two-sorted-lists merge. When recursion’s stack violates a space bound, convert divide-and-conquer to bottom-up iteration by making the subproblem size an explicit loop variable.