78. Sort List
mediumAsked at PlaidSort 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 Sam K., 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
head = [4,2,1,3][1,2,3,4]Example 2
head = [-1,5,3,4,0][-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.
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.