Quicksort for linked lists

Medium

Problem

Sort a linked list using quicksort, partitioning the nodes around a pivot by relinking them.

Example 1

Input:  10 → 30 → 3 → 4 → 20 → 5
Output: 3 → 4 → 5 → 10 → 20 → 30

Also asked as: Quicksort for Linked Lists

Test cases

Case 1

Input:    [10,30,3,4,20,5]
Expected: [3,4,5,10,20,30]

Case 2

Input:    [3,3,1]
Expected: [1,3,3]

Case 3

Input:    [1]
Expected: [1]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Partition around the head as pivot

Time O(n log n) avg, O(n²) worstSpace O(log n)

Build two sublists (< pivot, ≥ pivot) in one pass, recursively sort each, then concatenate. Works but merge sort is usually preferred for lists.

function quickSortList(head) {
if (!head || !head.next) return head;
const pivot = head.val;
let less = { next: null }, ge = { next: null };
let lt = less, gt = ge;
for (let n = head.next; n; n = n.next) {
if (n.val < pivot) { lt.next = n; lt = n; } else { gt.next = n; gt = n; }
}
lt.next = gt.next = null;
const sortedLess = quickSortList(less.next);
const sortedGe = quickSortList(ge.next);
head.next = sortedGe;
if (!sortedLess) return head;
let tail = sortedLess;
while (tail.next) tail = tail.next;
tail.next = head;
return sortedLess;
}