Skip to main content
Merge & Sort

Sort Linked List

Use merge sort: find the middle (fast/slow pointers), split into two halves, recursively sort each half, then merge them. This is O(n log n) time and O(log n) stack space.

O(n log n)
·
O(log n)

How It Works

Sorting a linked list rules out the usual array tools: quicksort needs random access for good pivots and heapsort needs indexing. Merge sort fits perfectly. Find the middle with fast and slow pointers, sever the list into two halves, recursively sort each, and merge them with the dummy-head relink merge. Splitting is O(n) per level, merging is O(n) per level, and there are O(log n) levels: O(n log n) total.

Space is O(log n) for the recursion stack — the merge itself allocates nothing, unlike array merge sort's O(n) buffer. A bottom-up variant merges runs of size 1, 2, 4, ... iteratively, reaching true O(1) auxiliary space, which is the standard follow-up.

Step-by-Step Visualization

Sort linked list: 4→2→1→3
4
0
2
1
1
2
3
3
StepFind middle, split
1/4

Code

Java
static ListNode sortList(ListNode head) {
  if (head == null || head.next == null) return head;

  ListNode slow = head, fast = head.next;
  while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

  ListNode mid = slow.next;
  slow.next = null; // Split

  ListNode left = sortList(head);
  ListNode right = sortList(mid);
  return mergeTwoLists(left, right);
}

Tips & Gotchas

1Use fast/slow to find middle, split into two halves
2Recursively sort each half, then merge
3Bottom-up merge sort can achieve O(1) space on linked lists

Practice Problems

  • 1Sort List
  • 2Merge Two Sorted Lists
  • 3Insertion Sort List
  • 4Merge k Sorted Lists

About the Merge & Sort Pattern

Combine sorted linked lists or sort an unsorted one. Unlike arrays, linked lists can be merged in O(1) extra space by re-pointing nodes.

Key insight

Most linked list problems are about pointer manipulation. Draw it out! Fast & slow pointers detect cycles and find midpoints. In-place reversal is the other core technique.

Common Linked List Interview Problems

  • Reverse Linked List
  • Merge Two Sorted Lists
  • Linked List Cycle
  • Remove Nth Node From End
  • LRU Cache
  • Reorder List

Frequently Asked Questions

Why is quicksort a poor fit for linked lists?

Median or random pivot selection requires O(1) indexing that lists lack, so pivots degrade and the worst case O(n²) becomes likely on adversarial or already-sorted input. Merge sort's split-and-merge only ever walks sequentially, which is exactly what lists do well.

Where do implementations of list merge sort usually break?

Forgetting to cut the link between the two halves — setting the node before the middle's next to null — so the left recursion consumes the entire list and never terminates. Off-by-one middle selection for two-node lists causes the same infinite recursion.

Is O(n log n) the best possible here?

For comparison-based sorting, yes — the information-theoretic lower bound applies to lists as much as arrays. The interesting axis is space: top-down recursion uses O(log n) stack, while the bottom-up iterative version achieves O(1) auxiliary space.