Problem Statement

Sort List

We are given a linked list and we have to sort it from smallest to largest. A linked list is a chain of nodes, where each node holds a value and a pointer to the next node. You cannot jump to the middle by index like you can with an array, you can only walk forward one node at a time. The trick that fits this perfectly is merge sort. Merge sort is a way of sorting that keeps splitting the data in half until each piece is tiny and trivially sorted, then merges the small sorted pieces back together in order. Merge sort loves linked lists because merging two sorted lists only means rewiring pointers, so it uses almost no extra memory. The plan: find the middle and split the list in two, sort each half, then merge the two sorted halves back together.

mediumLinked ListSortingLinked ListTime: O(n log n) · Space: O(log n)

Signals to notice

sort a linked list in O(n log n)merge sort natural for listsno random access needed

Brute force first

Convert to array, sort, rebuild — O(n log n) but O(n) space.

The key insight

Merge sort: split at middle (slow/fast), sort each half recursively, merge sorted halves. O(n log n) time, O(log n) stack space.

Trace it on `head = [4,2,1,3]`

split [4,2,1,3]: slow/fast walk -> slow stops at 2; mid=[1,3], cut into left=[4,2], right=[1,3]
sortList([4,2]): fast.next=null, no walk; mid=[2], cut into [4] and [2]
merge([4],[2]): 2<=4 -> take 2, then 4 -> [2,4]
sortList([1,3]): fast.next=null, no walk; mid=[3], cut into [1] and [3]
merge([1],[3]): 1<=3 -> take 1, then 3 -> [1,3]
merge([2,4],[1,3]): pick 1, pick 2, pick 3, attach rest 4 -> [1,2,3,4]
return [1,2,3,4]

What must stay true

Merge sort fits linked lists perfectly — merging two sorted lists is O(n) with O(1) extra space, and splitting at the middle uses slow/fast pointers.

Shape of the loop

function sortList(head):
  if head is null or single node: return head
  slow, fast = head, head.next
  while fast and fast.next: slow=slow.next; fast=fast.next.next
  mid = slow.next; slow.next = null        # split at middle
  return merge(sortList(head), sortList(mid))

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using quicksort — it needs random access for efficient partitioning, which lists lack. Merge sort's sequential access is ideal.

Linked List Pattern