68. Sort List
mediumAsked at WorkdaySort 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 Sam K., 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^5Follow-up: Can you sort the linked list in O(n log n) time and O(1) memory (i.e. constant space)?
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, sort array, rebuild
Push values into array, sort, rebuild list.
- Time
- O(n log n)
- Space
- O(n)
// works but uses O(n) extra spaceTradeoff: 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.
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.