Skip to main content

72. Sort List

mediumAsked at Datadog

Sort 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 Alex Chen, 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

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

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →