LeetCode-in-All
148. Sort List
Medium
Given the head of a linked list, return the list after sorting it in ascending order.
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: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Solution
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* slow = head;
ListNode* fast = head;
ListNode* pre = slow;
while (fast != nullptr && fast->next != nullptr) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr;
ListNode* first = sortList(head);
ListNode* second = sortList(slow);
ListNode* res = new ListNode(1);
ListNode* cur = res;
while (first != nullptr || second != nullptr) {
if (first == nullptr) {
cur->next = second;
break;
} else if (second == nullptr) {
cur->next = first;
break;
} else if (first->val <= second->val) {
cur->next = first;
first = first->next;
cur = cur->next;
} else {
cur->next = second;
second = second->next;
cur = cur->next;
}
}
return res->next;
}
};