Quicksort for linked lists
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: []
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;}