Skip to main content

148. Sort List

medium

Sort a singly linked list in O(n log n) time. Merge sort is the natural fit because it doesn't need random access — find the middle with slow/fast, recurse on each half, then reuse Merge Two Sorted Lists to stitch them back.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a linked list, return the list after sorting it in ascending order. Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Constraints

  • The number of nodes in the list is in the range [0, 5 * 10^4].
  • -10^5 <= Node.val <= 10^5

Examples

Example 1

Input
head = [4,2,1,3]
Output
[1,2,3,4]

Example 2

Input
head = [-1,5,3,4,0]
Output
[-1,0,3,4,5]

Example 3

Input
head = []
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Quicksort is awkward on linked lists. Merge sort is natural: split in half, recurse, merge.

Hint 2

Split the list at its middle using slow/fast pointers — remember to terminate the first half by setting prev.next = null before recursing.

Hint 3

For the O(1) extra-space follow-up, do merge sort bottom-up: merge runs of size 1, then 2, then 4, … iteratively over the list.

Solution approach

Reveal approach

Top-down merge sort with slow/fast splitting. Base case: if head is null or head.next is null, return head. Otherwise split the list in half: use slow = head, fast = head.next (note the offset so a 2-node list splits cleanly into 1+1), advance slow by one and fast by two until fast reaches the end. mid = slow.next; slow.next = null (terminates the first half). Recurse: left = sortList(head); right = sortList(mid). Merge the two sorted halves with the standard Merge Two Sorted Lists routine (dummy head, two-pointer compare). Return the merged head. O(n log n) time, O(log n) stack space. For O(1) extra space, switch to bottom-up: iterate merge sizes 1, 2, 4, … and merge consecutive runs in place — same time complexity, no recursion stack.

Complexity

Time
O(n log n)
Space
O(log n)

Related patterns

  • linked-list
  • divide-and-conquer
  • fast-slow-pointers
  • merge-sort

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Sort List and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →