Skip to main content

78. Sort List

mediumAsked at Plaid

Sort a linked list in O(n log n) time. Plaid asks this because sorting a stream of transactions that arrived as a linked list (from a bank-feed batch) before merging into the master ledger is exactly this primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid sort-then-merge variant.

Problem

Given the head of a linked list, return the list after sorting it in ascending order.

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. Collect to array, sort, rebuild

Dump values, sort, write back into the list.

Time
O(n log n)
Space
O(n)
function sortList(head) {
  const v = [];
  for (let n = head; n; n = n.next) v.push(n.val);
  v.sort((a, b) => a - b);
  let p = head;
  for (const x of v) { p.val = x; p = p.next; }
  return head;
}

Tradeoff: Works but allocates and ignores list structure.

2. Merge sort on the list

Find the middle (slow/fast pointers), split, recursively sort each half, merge.

Time
O(n log n)
Space
O(log n) recursion
function sortList(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head, prev = null;
  while (fast && fast.next) { prev = slow; slow = slow.next; fast = fast.next.next; }
  prev.next = null;
  const left = sortList(head);
  const right = sortList(slow);
  return merge(left, right);
}
function merge(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: Linked-list-native sort. The split via slow/fast pointers and the merge of two sorted lists is the canonical approach.

Plaid-specific tips

Plaid grades this on whether you reach for merge sort (linked-list-native) rather than dumping to an array. Bonus signal: discuss the bottom-up iterative variant that achieves O(1) extra space — useful for huge lists. Connect to merging batched feeds into a sorted master ledger.

Common mistakes

  • Forgetting to break the list in the middle (prev.next = null) — infinite recursion.
  • Using shift/unshift in the merge — works but slower than splicing existing nodes.
  • Using >= instead of <= — flips stability when ties matter (e.g., transactions with equal timestamps must keep original order).

Follow-up questions

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

  • Bottom-up iterative merge sort — O(1) extra space.
  • Sort a doubly-linked list.
  • Merge k sorted lists (LC 23).

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 merge sort, not quicksort?

Merge sort is naturally stable and works well on linked lists (random-access isn't needed). Quicksort needs partition by index, which linked lists don't support efficiently.

Why slow/fast for the middle?

Slow moves 1 step per iteration; fast moves 2. When fast hits the end, slow is at the middle. No need to know the length upfront.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →