250. Quicksort on a Linked List

A singly linked list contains n integer values in no particular order. Sort it using the quicksort algorithm (pick a pivot, partition the list around it, then recursively sort the partitions) and print the sorted values.

Input: The first line contains an integer n. The second line contains n space-separated integers, the linked list's values in order. Output: Print the sorted values, space-separated, on one line.

1 <= n <= 10^5

Picking the LAST or FIRST node as pivot (rather than some 'middle' element, which isn't O(1) accessible in a linked list) is a necessary adaptation - this makes worst-case behavior (O(n²)) more likely on already-sorted or adversarial inputs compared to array quicksort with a randomized pivot.

Sort a linked list using the quicksort algorithm, adapted to work without array indexing. Brute force: Copy all values into an array, quicksort the array using standard index-based swapping, and rebuild the list - this works but doesn't demonstrate adapting quicksort's PARTITIONING step to work without random access, which is the actual point of this exercise. Optimised: Building explicit 'less than' and 'greater or equal' sub-lists (by relinking nodes as you scan, rather than swapping elements by index) replicates quicksort's partitioning logic in a way that works naturally on linked lists, which have no O(1) random access needed for typical index-based partitioning.

Traverse the linked list once to copy all its values into an array, sort that array with a standard efficient sort, then rebuild a new linked list (or overwrite the existing nodes' values) from the sorted array in list order. This produces a correct sorted list but requires an entire auxiliary array the size of the list, which sidesteps rather than embraces the linked-list structure. Time: O(n log n) average Space: O(n)

Perform quicksort natively on the linked list: pick the first node as the pivot, then walk the rest of the list splitting nodes into a 'less than pivot' list and a 'greater than or equal to pivot' list by relinking pointers (no array conversion, no new node allocation), recursively sort each sublist the same way, and concatenate less-list + pivot + greater-list. This works directly on pointers and avoids the full array copy, but a fixed first-element pivot degrades badly (to quadratic time) on already-sorted or adversarially ordered lists. Time: O(n log n) average, O(n^2) worst case Space: O(log n) recursion stack

Use the same in-place pointer-relinking partition scheme as the better approach, but select the pivot randomly (or via median-of-three sampling of a few nodes) instead of always taking the first node. This makes the O(n^2) worst case extremely unlikely regardless of the input's original order, since an adversary can no longer predict which element will be chosen as pivot, giving expected O(n log n) performance robustly even on already-sorted input where the fixed-pivot version would be at its worst. Time: O(n log n) expected Space: O(log n) recursion stack

1. Pick a PIVOT node (commonly the last or first node of the current sub-list, since a linked list has no convenient 'middle' index access). 2. Partition by building TWO sub-lists - one for values LESS than the pivot, one for values GREATER OR EQUAL - by relinking nodes into each, rather than swapping array elements. 3. Recursively sort each sub-list, then relink them around the pivot node to form the final sorted result.

Time: O(n log n) average case, O(n²) worst case (e.g. with an already-sorted list and a poor pivot choice) - the same complexity profile as array-based quicksort. Space: O(log n) average recursion depth, O(n) worst case.

n = 1 (trivially sorted); n = 10^5 for performance; already-sorted or reverse-sorted input, and repeated values, since the constraints don't rule out duplicates.

Be ready to explain explicitly WHY quicksort's usual advantage (fast in-place swaps by array index) doesn't apply to linked lists - this is exactly why merge sort is generally preferred for linked lists in practice, despite quicksort often being faster on arrays.