在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4示例 2:
输入: -1->5->3->4->0 输出: -1->0->3->4->5
解法一：
//时间复杂度O(nlogn), 空间复杂度O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeList(ListNode* p1, ListNode* p2) {//将p1、p2合并
ListNode* temp = new ListNode(-1);
ListNode* p3 = temp;
while(p1 && p2) {
if(p1->val > p2->val) swap(p1, p2);
p3->next = p1;
p1 = p1->next;
p3->next->next = nullptr;
p3 = p3->next;
}
if(p1) p3->next = p1;
else if(p2) p3->next = p2;
return temp->next;
}
ListNode* sortList(ListNode* head) {
if(!head) return nullptr;//空链表
if(!head->next) return head;//只有一个元素
if(!head->next->next) {//只有两个元素
if(head->val > head->next->val) {
head->next->next = head;
head = head->next;
head->next->next = nullptr;
}
return head;
}
//至少三个元素
ListNode *p1 = head, *p2 = head;
while(p2 && p2->next && p2->next->next) {
p1 = p1->next;
p2 = p2->next->next;
}
p2 = p1->next;
p1->next = nullptr;//将链表分为head和p2两部分，len(head) == len(p2) 或 len(head) = len(p2) + 1
head = sortList(head);
p2 = sortList(p2);
return mergeList(head, p2);
}
};解法一：
归并排序。在每一个递归层次，对当前链表一分为二（O(nlogn)），分别对左、右两部分进行归并排序，然后再将两部分合并（O(n)）为一条。
终止条件是链表元素剩余小于3。
在每一个递归层次里，找中点这个操作要O(n)，合并这个操作也要O(n)。递归树一共有logn层，所以时间复杂度为O(nlogn)。
2019/12/26 13:49