Skip to main content

68. Sort List

mediumAsked at Workday

Sort a linked list in O(n log n) time and O(1) auxiliary space. Workday uses this for merge-sort-on-linked-lists fluency — same shape as merge-sorting an audit-log linked stream without buffering.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 onsite.

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
  • Follow-up: Can you sort the linked list in O(n log n) time and O(1) memory (i.e. constant space)?

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

Push values into array, sort, rebuild list.

Time
O(n log n)
Space
O(n)
// works but uses O(n) extra space

Tradeoff: Fails the follow-up.

2. Top-down merge sort (recursive)

Split with slow/fast pointers, sort halves, merge.

Time
O(n log n)
Space
O(log n) stack)
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) stack — not truly O(1) space. Bottom-up iterative would give true O(1).

Workday-specific tips

Workday accepts O(log n) stack. The bottom-up iterative version is the true O(1)-space answer if they push on the follow-up — mention it. The slow/fast split is standard, but remember to cut prev.next before recursing.

Common mistakes

  • Forgetting to cut prev.next = null — left half still points into right half.
  • Using slow.next as the split point — splits in the wrong half.
  • Reaching for Array.from + sort — defeats the purpose.

Follow-up questions

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

  • Bottom-up iterative merge sort for true O(1) space.
  • Merge K Sorted Lists (LC 23) — uses merge as primitive.
  • Insertion Sort List (LC 147).

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 slow/fast for split?

Standard trick for finding the middle of a linked list in one pass. Slow steps once, fast steps twice — when fast reaches the end, slow is at the middle.

True O(1) space?

Bottom-up iterative merge sort. Sort in chunks of 1, then 2, then 4... merging pairs at each level. No recursion.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →