Skip to main content

80. Sort List

mediumAsked at Vercel

Sort a linked list in O(n log n) time and O(1) extra space. Vercel asks this for the merge-sort-on-linked-list pattern — same skill as efficiently merging per-region log streams without random access.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; merge sort on linked list expected.
  • Blind (2026-Q1)— Listed in Vercel runtime engineer screen.

Problem

Given the head of a linked list, return the list after sorting it in ascending order. Can you sort the linked list in O(n log n) 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]

Approaches

1. Dump to array, sort, rebuild

Collect values, Array.sort, rebuild list.

Time
O(n log n)
Space
O(n)
// O(n) extra space. Vercel wants O(log n) at most (recursion stack).

Tradeoff: Easy but uses linear extra space.

2. Top-down merge sort (recursive)

Find middle (fast/slow); recursively sort each half; merge.

Time
O(n log n)
Space
O(log n) stack
function sortList(head) {
  if (!head || !head.next) return head;
  // Find middle
  let slow = head, fast = head.next;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  const mid = slow.next;
  slow.next = null;
  // Recurse and merge
  const left = sortList(head);
  const right = sortList(mid);
  return mergeTwo(left, right);
}
function mergeTwo(a, b) {
  const dummy = { next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

Tradeoff: O(log n) recursion stack. Bottom-up version is O(1) stack but more code.

Vercel-specific tips

Vercel grades the merge-sort and the middle-finding (fast.next start at head.next, not head — gives correct rounding). Bonus signal: offering the bottom-up iterative version for true O(1) space. Articulate the merge-sort phases out loud.

Common mistakes

  • Forgetting to null-terminate slow.next — both halves still share the tail.
  • Starting fast at head instead of head.next — produces uneven splits.
  • Calling mergeTwo with one head, not two halves — wrong split.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Bottom-up merge sort — O(1) stack space.
  • Merge k sorted lists (LC 23, hard).
  • Quicksort on linked list — possible but ugly.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why fast.next, not fast?

Starting fast at head.next means when the list has even length, slow ends up at the FIRST middle element. This gives the cleaner split into two equal halves.

Why merge sort and not quicksort?

Merge sort doesn't need random access, perfect for linked lists. Quicksort's partitioning is awkward without indices. Merge sort is also stable.

Practice these live with InterviewChamp.AI

Drill Sort List and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →