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 entirely: 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
class Solution:
def sortList(self, 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 bound is fine — what kills it is the O(n) auxiliary array: the follow-up (and the interviewer) explicitly asks for constant extra space, and it sidesteps the linked-list manipulation the problem is testing.
Approach 2 — Top-down merge sort
The insight: merge sort is the one 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. Merge sort is the divide-and-conquer algorithm that sorts by halving the input, sorting each half, and merging the two sorted halves. Find the middle with slow/fast pointers, cut the list there, recurse on each half, merge.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
class Solution:
def sortList(self, 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 = self.sortList(head)
right = self.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)
The insight: recursion is only there to discover the run boundaries. If you instead fix the run length explicitly — merge runs of length 1, then 2, then 4, … — you get the same merge tree iteratively with zero 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
class Solution:
def sortList(self, 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 = self.split(left, step)
curr = self.split(right, step)
prev = self.merge(left, right, prev)
step *= 2
return dummy.next
def split(self, 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(self, 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
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 reorganize a linked list wholesale, ask which classic algorithm works with only sequential access — merge sort is the canonical answer, built from two reusable primitives you’ll use again and again: slow/fast middle-finding and the two-sorted-lists merge. And 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.