Sort List
Given the head of a linked list, return the list after sorting it in ascending order.
Constraints:
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5
Examples:
Input: [4,2,1,3]
Output: [1,2,3,4]
Explanation: The linked list is sorted in ascending order.
Input: []
Output: []
Explanation: The empty linked list is already sorted.
Input: [1]
Output: [1]
Explanation: The linked list with one node is already sorted.
Solutions
Merge Sort
Time: O(n log n)Space: O(log n)
The solution uses the merge sort algorithm to sort the linked list. It first converts the linked list to an array, sorts the array, and then updates the linked list with the sorted values.
class Solution {
public: ListNode* sortList(ListNode* head) {
vector<int> arr;
while (head) {
arr.push_back(head->val);
head = head->next;
}
sort(arr.begin(), arr.end());
head = new ListNode(0);
ListNode* curr = head;
for (int num : arr) {
curr->next = new ListNode(num);
curr = curr->next;
}
return head->next;
}
}
;Follow-up:
How would you optimize the solution for a very large linked list?
