148. Sort List
1. Description
Given the head of a linked list, return the list after sorting it in ascending order.
2. Example
Example 1
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3
Input: head = []
Output: []
3. Constraints
- The number of nodes in the list is in the range [0, 5 * 10$^4$].
- -10$^5$ <= Node.val <= 10$^5$
4. Solutions
Bottom-Up Merge Sort
n is the number of nodes in the head
Time complexity: O(nlogn)
Space complexity: O(1)
class Solution {
public:
ListNode *sortList(ListNode *head) {
ListNode dummy(0, head);
int length = 0;
for (auto iter = dummy.next; iter != nullptr; iter = iter->next) {
++length;
}
for (int sub_length = 1; sub_length < length; sub_length <<= 1) {
ListNode *prev = &dummy, *current = dummy.next;
while (current != nullptr) {
ListNode *head1 = current;
for (int i = 1; i < sub_length && current->next != nullptr; ++i) {
current = current->next;
}
ListNode *head2 = current->next;
current->next = nullptr;
current = head2;
if (current != nullptr) {
for (int i = 1; i < sub_length && current->next != nullptr; ++i) {
current = current->next;
}
}
ListNode *next = nullptr;
if (current != nullptr) {
next = current->next;
current->next = nullptr;
}
prev->next = merge(head1, head2);
while (prev->next != nullptr) {
prev = prev->next;
}
current = next;
}
}
return dummy.next;
}
private:
ListNode *merge(ListNode *head1, ListNode *head2) {
ListNode dummy;
ListNode *iter = &dummy;
while (head1 != nullptr && head2 != nullptr) {
if (head1->val <= head2->val) {
iter->next = head1;
head1 = head1->next;
} else {
iter->next = head2;
head2 = head2->next;
}
iter = iter->next;
}
iter->next = (head1 == nullptr ? head2 : head1);
return dummy.next;
}
};