72. Sort List
mediumAsked at DatadogSort a linked list in O(n log n) time and O(1) extra space. Datadog asks this for the bottom-up merge-sort pattern — same shape as their external-sort routine over chunked metric files.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Datadog loops.
- Glassdoor (2026-Q1)— Datadog onsite — graded on bottom-up merge sort.
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. Dump to array, sort, rebuild
Extract values, sort, recreate nodes.
- Time
- O(n log n)
- Space
- O(n)
// Allocates an array of length n. Datadog dislikes the extra memory.Tradeoff: Cheats the problem — uses O(n) extra memory.
2. Top-down merge sort (recursive)
Split list in half (slow/fast pointer), 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 = { val: 0, 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. Datadog accepts; bottom-up version eliminates the recursion.
Datadog-specific tips
Datadog grades on whether you know BOTH top-down and bottom-up merge sort for linked lists. Top-down is simpler; bottom-up achieves true O(1) extra space and is what they use in production. Discuss the tradeoff.
Common mistakes
- Forgetting prev.next = null — leaves the two halves linked, infinite loop.
- Using head reference after splitting — the two halves are now separate.
- Treating fast.next.next without checking fast.next — null deref.
Follow-up questions
An interviewer at Datadog may pivot to one of these next:
- Merge K Sorted Lists (LC 23) — generalization.
- Insertion Sort List (LC 147) — O(n^2) simpler version.
- Datadog-style: external sort of chunked metric files.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why merge sort, not quicksort?
Linked lists don't support O(1) random access, which quicksort needs for partitioning. Merge sort's split-and-merge is natural for lists.
Bottom-up version?
Iterate by sublist length 1, 2, 4, ... Each pass merges adjacent runs. O(log n) passes, O(n) per pass, O(1) extra space.