插入排序: O(n^2)
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (head) {
ListNode* tmp = head->next;
cur = dummy;
while (cur->next && cur->next->val <= head->val) {
cur = cur->next;
}
head->next = cur->next;
cur->next = head;
head = tmp;
}
ListNode* result = dummy->next;
delete dummy;
return result->next;
}
};
歸并排序:O(nlogn)
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next)
return head;
ListNode *slow = head, *fast = head, *pre = head;
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
return merge(sortList(head), sortList(slow));
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(INT_MIN);
ListNode *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
}
else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1)
cur->next = l1;
if (l2)
cur->next = l2;
ListNode *result = dummy->next;
delete dummy;
return result;
}
};