Quicksort for Linked Lists [Very Important]
QuickSort for Linked Lists
Problem Statement
Given a linked list, sort it using the QuickSort algorithm. Unlike arrays where QuickSort is preferred, for linked lists, merge sort is usually better. However, understanding QuickSort for linked lists is valuable for interviews.
Example
Input: 3 -> 1 -> 4 -> 1 -> 5 -> 9 -> 2 -> null
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 5 -> 9 -> null
Input: 5 -> 4 -> 3 -> 2 -> 1 -> null
Output: 1 -> 2 -> 3 -> 4 -> 5 -> null
Understanding QuickSort on Linked Lists
Key Differences from Array QuickSort
- No random access: Can't directly access pivot by index
- Partitioning: Can't swap elements in place easily
- Approach: Usually take last element as pivot, or partition around pivot value
Two Main Approaches
- By changing links: Rearrange nodes by modifying next pointers
- By swapping values: Simpler but not "true" linked list QuickSort
Approach 1: QuickSort by Swapping Values
Intuition
Similar to array QuickSort - use the last node as pivot, partition by swapping values, and recursively sort.
Algorithm
- Take the last element as pivot
- Partition: Move all smaller elements before pivot
- Recursively sort left and right partitions
Implementation
Complexity Analysis
- Time Complexity: O(n²) worst case, O(n log n) average
- Space Complexity: O(log n) for recursive call stack
Approach 2: QuickSort by Rearranging Links (True QuickSort)
Intuition
Instead of swapping values, rearrange the nodes themselves by modifying the links. This is the "true" linked list way but more complex.
Algorithm
- Choose pivot (typically first or last node)
- Partition into three lists: smaller, equal, greater
- Recursively sort smaller and greater lists
- Concatenate: smaller + equal + greater
Implementation
Complexity Analysis
- Time Complexity: O(n²) worst case, O(n log n) average
- Space Complexity: O(log n) for recursive call stack
QuickSort vs Merge Sort for Linked Lists
| Aspect | QuickSort | Merge Sort | |--------|-----------|------------| | Average Time | O(n log n) | O(n log n) | | Worst Time | O(n²) | O(n log n) | | Space | O(log n) | O(log n) or O(1) | | Stability | No | Yes | | Cache Performance | Poor | Better | | Recommended | No | Yes |
Why Merge Sort is Preferred
- Guaranteed O(n log n): No worst-case O(n²)
- Stable sort: Equal elements maintain relative order
- Easier implementation: Finding middle is straightforward
- Better for linked lists: Merging is efficient without extra space
Key Takeaways
- Merge Sort is preferred for linked lists in practice
- QuickSort for linked lists is more of an academic exercise
- The partition step is more complex for linked lists
- Three-way partition (less, equal, greater) handles duplicates well
- Swapping values is simpler but doesn't truly manipulate the structure
- Understanding both approaches shows deep understanding of algorithms
- In interviews, mention that Merge Sort is better for linked lists