Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
本题要求用O(nlogn)的时间复杂度和常数空间复杂度对一个链表排序。 O(nlgn)的排序算法有快速排序、堆排序、归并排序，快排和堆排都需要对元素的随机访问，不适用于链表，这里我们可以用归并排序实现。 归并的思路是不断把链表对分成两个子链表，直到只剩一个节点，此时一个节点是有序的，然后不断的两两归并，mergeList就好办多了。 完整代码如下：
class Solution {
private:
ListNode* mergeList(ListNode* h1, ListNode* h2)
{
if (!h1)
return h2;
else if (!h2)
return h1;
ListNode *head = new ListNode(0), *h = head;
while (h1 && h2) {
if (h1->val < h2->val) {
h->next = h1;
h1 = h1->next;
}
else {
h->next = h2;
h2 = h2->next;
}
h = h->next;
}
if (h1)
h->next = h1;
else if (h2)
h->next = h2;
return head->next;
}
public:
ListNode* sortList(ListNode* head)
{
if (!head || !head->next)
return head;
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
ListNode* left = sortList(head);
ListNode* right = sortList(fast);
return mergeList(left, right);
}
};本代码提交AC，用时56MS。
二刷，归并排序还可以写得简单点：
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL)return head;
ListNode *slow = head, *fast = head, *pre = head;
while (fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
ListNode *left = sortList(head), *right = sortList(slow);
ListNode *dummy = new ListNode(0);
ListNode *lst = dummy;
while (left != NULL || right != NULL) {
int l = left != NULL ? left->val : INT_MAX;
int r = right != NULL ? right->val : INT_MAX;
if (l < r) {
lst->next = left;
left = left->next;
}
else {
lst->next = right;
right = right->next;
}
lst = lst->next;
}
return dummy->next;
}
};本代码提交AC，用时44MS。