[LeetCode 148] Sort List

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

Diffculty
Medium

Similar Problems
[LeetCode ] Merge Two Sorted Lists Easy [LeetCode ] Sort Colors Medium [LeetCode ] Insertion Sort List Medium

Analysis

题解1 - 归并排序(链表长度求中间节点)

链表的排序操作，对于常用的排序算法，能达到 O(NLogN)O(n\log n)O(nlogn)的复杂度有快速排序(平均情况)，归并排序，堆排序。快速排序不一定能保证其时间复杂度一定满足要求，归并排序和堆排序都能满足复杂度的要求。 在数组排序中，归并排序通常需要使用 O(n)O(n)O(n) 的额外空间，也有原地归并的实现，代码写起来略微麻烦一点。但是对于链表这种非随机访问数据结构，所谓的「排序」不过是指针 next 值的变化而已，主要通过指针操作，故仅需要常数级别的额外空间，满足题意。堆排序通常需要构建二叉树，在这道题中不太适合。

既然确定使用归并排序，我们就来思考归并排序实现的几个要素。

• 按长度等分链表，归并虽然不严格要求等分，但是等分能保证线性对数的时间复杂度。由于链表不能随机访问，故可以先对链表进行遍历求得其长度。
• 合并链表，细节已在 Merge Two Sorted Lists 中详述。 在按长度等分链表时进行「后序归并」———— 先求得左半部分链表的表头，再求得右半部分链表的表头，最后进行归并操作。 由于递归等分链表的操作需要传入链表长度信息，故需要另建一辅助函数。

Solutions

class Solution { public: ListNode sortList(ListNode head) { if (head == nullptr) return nullptr; int len = 0; ListNode *node = head; while (node != nullptr) { node = node->next; ++len; } return sortListHelper(head, len); }

private: ListNode sortListHelper(ListNode head, const int length) { if ((nullptr == head) || (length <= 0)) { return head; }

    ListNode *midNode = head;
    int count = 1;
    while (count < length / 2) {
        midNode = midNode->next;
        ++count;
    }

    ListNode *rList = sortListHelper(midNode->next, length - length / 2);
    midNode->next = nullptr;
    ListNode *lList = sortListHelper(head, length / 2);

    return mergeList(lList, rList);
}

ListNode *mergeList(ListNode *l1, ListNode *l2) {
    ListNode *dummy = new ListNode(0);
    ListNode *lastNode = dummy;
    while ((nullptr != l1) && (nullptr != l2)) {
        if (l1->val < l2->val) {
            lastNode->next = l1;
            l1 = l1->next;
        } else {
            lastNode->next = l2;
            l2 = l2->next;
        }

        lastNode = lastNode->next;
    }

    lastNode->next = (nullptr != l1) ? l1 : l2;
    return dummy->next;
}

};

源码分析

归并子程序没啥好说的了，见 Merge Two Sorted Lists. 在递归处理链表长度时，分析方法和 [Convert Sorted List to Binary Search Tree][] 一致，count表示遍历到链表中间时表头指针需要移动的节点数。在纸上分析几个简单例子后即可确定，由于这个题需要的是「左右」而不是二叉搜索树那道题需要三分——「左中右」，故将count初始化为1更为方便，左半部分链表长度为length / 2, 这两个值的确定最好是先用纸笔分析再视情况取初值，不可死记硬背。 找到中间节点后首先将其作为右半部分链表处理，然后将其next值置为nullptr, 否则归并子程序无法正确求解。这里需要注意的是midNode是左半部分的最后一个节点，midNode->next才是链表右半部分的起始节点。 递归模型中左、右、合并三者的顺序可以根据分治思想确定，即先找出左右链表，最后进行归并(因为归并排序的前提是两个子链表各自有序)。 复杂度分析

遍历求得链表长度，时间复杂度为 O(n)O(n)O(n), 「折半取中」过程中总共有 log(n)\log(n)log(n) 层，每层找中点需遍历 n/2n/2n/2 个节点，故总的时间复杂度为 n/2⋅O(logn) n/2 \cdot O(\log n)n/2⋅O(logn) (折半取中), 每一层归并排序的时间复杂度介于 O(n/2)O(n/2)O(n/2) 和 O(n)O(n)O(n)之间，故总的时间复杂度为 O(nlogn)O(n \log n)O(nlogn), 空间复杂度为常数级别，满足题意。

题解2 - 归并排序(快慢指针求中间节点)

除了遍历链表求得总长外，还可使用看起来较为巧妙的技巧如「快慢指针」，快指针每次走两步，慢指针每次走一步，最后慢指针所指的节点即为中间节点。使用这种特技的关键之处在于如何正确确定快慢指针的起始位置。

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (nullptr == head || nullptr == head->next) {
            return head;
        }

        ListNode *midNode = findMiddle(head);
        ListNode *rList = sortList(midNode->next);
        midNode->next = nullptr;
        ListNode *lList = sortList(head);

        return mergeList(lList, rList);
    }

private:
    ListNode *findMiddle(ListNode *head) {
        if (nullptr == head || nullptr == head->next) {
            return head;
        }
        ListNode *slow = head, *fast = head->next;
        while(nullptr != fast && nullptr != fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode *mergeList(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *lastNode = dummy;
        while ((nullptr != l1) && (nullptr != l2)) {
            if (l1->val < l2->val) {
                lastNode->next = l1;
                l1 = l1->next;
            } else {
                lastNode->next = l2;
                l2 = l2->next;
            }
            lastNode = lastNode->next;
        }

        lastNode->next = (nullptr != l1) ? l1 : l2;
        return dummy->next;
    }
};

源码分析

异常处理不仅考虑了head, 还考虑了head->next, 可减少辅助程序中的异常处理。 使用快慢指针求中间节点时，将fast初始化为head->next可有效避免无法分割两个节点如1->2->nullptrfast_slow_pointer。 求中点的子程序也可不做异常处理，但前提是主程序sortList中对head->next做了检测。 最后进行merge归并排序。 **> 在递归和迭代程序中，需要尤其注意终止条件的确定，以及循环语句中变量的自增，以防出现死循环或访问空指针。

复杂度分析

同上。