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) {
int length = 0;
for (auto iter = head; iter != nullptr; iter = iter->next) {
++length;
}
ListNode dummy(0, head);
for (int len = 1; len < length; len <<= 1) {
ListNode *tail = &dummy;
while (tail->next != nullptr) {
ListNode *l1_head = tail->next;
ListNode *curr = l1_head;
for (int i = 1; i < len && curr->next != nullptr; ++i) {
curr = curr->next;
}
ListNode *l2_head = curr->next;
curr->next = nullptr;
curr = l2_head;
if (curr == nullptr) {
break;
}
for (int i = 1; i < len && curr->next != nullptr; ++i) {
curr = curr->next;
}
ListNode *backup = curr->next;
curr->next = nullptr;
auto [new_head, new_tail] = merge_two_lists(l1_head, l2_head);
tail->next = new_head;
tail = new_tail;
new_tail->next = backup;
}
}
return dummy.next;
}
private:
pair<ListNode *, ListNode *> merge_two_lists(ListNode *l1, ListNode *l2) {
ListNode dummy;
auto tail = &dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 == nullptr ? l2 : l1;
while (tail->next != nullptr) {
tail = tail->next;
}
return {dummy.next, tail};
}
};