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 Sam K., 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

More Linked Lists practice problems

See all Linked Lists problems →