题解 | #单链表的排序#

NC70 单链表的排序

题意

给定一个无序单链表，实现单链表的排序(按升序排序)。

1. 值排序

这是一个偷懒的做法，我们可以遍历整个链表，把值放到数组中，再sort，再重新填进去。

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        vector<int> nums;
        ListNode* temp = head;

        // 遍历一遍链表
        while (temp) {
            nums.push_back(temp->val);
            temp = temp->next;
        }

        // 对值排序
        sort(nums.begin(), nums.end());

        // 重新填回去
        temp = head;
        for (int i = 0; i < nums.size(); i++) {
            temp->val = nums[i];
            temp = temp->next;
        }
        return head;
    }
};

时间复杂度： $O(nlogn)$ , 依赖于 STL sort的时间复杂度
空间复杂度： $O(n)$ , 定义了长度为 $n$ 的链表nums。

2. 归并排序

我们看单链表的性质，有去无回，那么我们可以利用归并排序的思路，先找到单链表的中点，再递归排序左右两侧，再合并。具体实现思路如下：（这个思路很重要，是两个单链表基础算法的融合）

2.1 寻找单链表中点

这是归并排序中的一个子问题，也同样是单链表中比较重要的基础算法。与 NC69 链表中倒数最后k个结点 类似，也是采用快慢指针法。

定义两个指针，较快的每次走两步，较慢的每次走一步
快指针走到头的时候，慢指针指向中点。
对左右两半递归调用排序算法。

2.2 合并两个有序链表为一个有序链表

双指针法，先定义辅助变量pHead，指向新链表头部。接下来如下操作：

定义两个指针i和j，分别指向两个有序链表的头部。
如果i的值更小，则i右移，新节点串入pHead右侧，否则j右移。
最后，i和j哪个有后继节点，就把哪个直接串入pHead右侧。

算法流程如下图所示。

图片说明

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    // C++11中允许使用using关键字定义别名
    using PNode = ListNode*;
    ListNode* sortInList(ListNode* head) {
        if (!head || !head->next) return head;

        // 2.1 快慢指针找中点
        PNode fast = head->next, slow = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 这里需要注意，实现的时候需要把左半边“封口”，并缓存下右半边的起点
        PNode temp = slow->next;
        slow->next = nullptr;

        // 递归两边
        PNode left = sortInList(head), right = sortInList(temp);

        // 2.2 合并两个有序单链表为一个
        // 这里需要设立一个虚拟节点(dummy head)，否则不知道头在哪，返回虚节点的next即可
        PNode dh = new ListNode(0), cur = dh; //cur指针从dummy head开始

        // 合并过程
        while (left && right) {
            if (left->val < right->val) {
                cur->next = left;
                left = left->next;
            } else {
                cur->next = right;
                right = right->next;
            }

            cur = cur->next;
        }

        // 如果哪一段还有剩余，直接连到cur后面
        if (left) cur->next = left;
        else if (right) cur->next = right;

        // dh是虚拟头部节点，需要返回其后继
        return dh->next;
     }
};

时间复杂度： $O(nlogn)$
空间复杂度： $O(logn)$ . 如上图所示，算法的递归深度最多为 $logn$ ，每一层递归调用中，没有使用额外数组，所以每层的空间复杂度为 $O(1)$ , 整体空间复杂度为 $logn$ .