[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;
    }
};