[Leetcode] 148. Sort List 解题报告

题目：

Sort a linked list in O(n log n) time using constant space complexity.

思路：

提到O(nlogn)时间复杂度的排序，我们很容易想到的就是快速排序和归并排序。虽然快速排序在实践中的平均速度特别快，但是它在最坏情况下的时间复杂度却高达O(n^2)。

归并排序是最中规中矩的一种排序方法。虽然由于会用到递归，在实际计算机中占用的栈空间为O(logn)，但是在算法分析中，我们往往也将其视为常数空间复杂度。因此，采用归并排序来解决本题目是符合要求的。

首先利用快慢指针把链表均衡地一分为二，然后分别递归排序；最后是最关键的合并这一步骤，请见下面的代码片段。最后别忘了利用虚拟头结点这一神器^_^。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
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;      // separate the LinkedList
        slow->next = NULL;
        ListNode *p = sortList(head), *q = sortList(fast);
        ListNode *pre_head = new ListNode(0);
        ListNode *temp_node = pre_head;
        while (p || q) {
            if (!q || (p && p->val < q->val)) {
                temp_node->next = p;
                p = p->next;
            }
            else {
                temp_node->next = q;
                q = q->next;
            }
            temp_node = temp_node->next;
        }
        head = pre_head->next;
        delete pre_head;
        return head;
    }
};