You are given a Linked List. Sort the given Linked List using quicksort.
Examples:
Input: Linked list: 1->6->2
Output: 1->2->6
Explanation:
After sorting the nodes, we have 1, 2 and 6.
Input: Linked list: 1->9->3->8
Output: 1->3->8->9
Explanation:
After sorting the nodes, we have 1, 3, 8 and 9.
Constraints:
1<= size of linked list <= 105
Approach 01:
-
C++
-
Python
class Solution {
public:
struct Node* quickSort(struct Node* head) {
// Return head after sorting the linked list
auto sort = [](Node* start, Node* end, auto& sort) -> Node* {
if (!start || start == end || start->next == end)
return start;
int pivotValue = start->data;
Node pivotDummy(0);
pivotDummy.next = start;
Node* prev = &pivotDummy;
Node* current = start;
while (current != end) {
Node* nextNode = current->next;
if (current->data < pivotValue) {
prev->next = current->next;
current->next = pivotDummy.next;
pivotDummy.next = current;
} else {
prev = prev->next;
}
current = nextNode;
}
start->next = sort(start->next, end, sort);
return sort(pivotDummy.next, start, sort);
};
return sort(head, nullptr, sort);
}
};
Time Complexity
- Partitioning:
Each recursive call to the
sortfunction partitions the list around a pivot node, separating nodes smaller than the pivot to one side and those greater than or equal to it to the other. In the worst case, partitioning takes \(O(n)\) time at each recursive level, where \(n\) is the number of nodes in the current sublist. - Recursive Calls:
The depth of recursive calls depends on the choice of pivot. In the best and average cases (balanced partitioning), there are \(O(\log n)\) recursive levels, while in the worst case (e.g., already sorted or reverse-sorted list), the recursion depth can go up to \(O(n)\).
- Overall Time Complexity:
In the average case, the time complexity is \(O(n \log n)\) due to balanced partitioning. However, in the worst case, the time complexity can degrade to \(O(n^2)\).
Space Complexity
- Recursive Call Stack:
Since each recursive call handles a portion of the list, the recursive stack space depends on the recursion depth. In the best and average cases (balanced partitions), the recursion depth is \(O(\log n)\), resulting in \(O(\log n)\) space complexity. In the worst case, recursion depth can reach \(O(n)\), resulting in \(O(n)\) space complexity.
- Auxiliary Storage:
This implementation sorts in-place on the linked list, so it doesn't require additional data structures for storage beyond the recursive stack.
- Overall Space Complexity:
The space complexity is \(O(\log n)\) in the average case due to the call stack and \(O(n)\) in the worst case.
def quickSort(head):
# Return head after sorting the linked list
def sort(start, end):
if not start or start == end or start.next == end:
return start
pivotValue = start.data
pivotDummy = Node(0)
pivotDummy.next = start
prev, current = pivotDummy, start
while current != end:
nextNode = current.next
if current.data < pivotValue:
prev.next = current.next
current.next = pivotDummy.next
pivotDummy.next = current
else:
prev = prev.next
current = nextNode
start.next = sort(start.next, end)
return sort(pivotDummy.next, start)
return sort(head, None)
Time Complexity
- Partitioning:
Each recursive call to
sortpartitions the list around a pivot node, placing elements smaller than the pivot before it and elements greater than or equal to it after. In the worst case, partitioning takes \(O(n)\) time for each level of recursion, where \(n\) is the number of nodes in the linked list. - Recursive Calls:
The algorithm may need up to \(O(n)\) recursive calls in the worst case if the list is already sorted or nearly sorted, resulting in a depth of recursion up to \(O(n)\).
- Overall Time Complexity:
In the average case, the time complexity is \(O(n \log n)\) due to balanced partitioning. However, in the worst case (e.g., already sorted list), the time complexity can degrade to \(O(n^2)\).
Space Complexity
- Recursive Call Stack:
The recursive depth can go up to \(O(\log n)\) in the average case due to balanced partitioning, leading to an \(O(\log n)\) space complexity in terms of recursive stack space.
In the worst case (unbalanced partitions), the recursion depth can reach up to \(O(n)\), resulting in \(O(n)\) space complexity due to the call stack.
- Auxiliary Storage:
This implementation operates directly on the linked list without creating additional data structures for storage, so no extra space is required beyond the recursive call stack.
- Overall Space Complexity:
The space complexity is \(O(\log n)\) in the average case due to the recursive call stack and \(O(n)\) in the worst case.