题解 | #单链表的排序#

题目的主要信息：

给定一个无序链表，要将其排序为升序数组

方法一：转化为数组排序

具体做法：

链表最难受的就是不能按照下标访问，只能逐个遍历，那像排序中常规的快速排序、堆排序都不能用了，只能用依次遍历的冒泡排序、选择排序这些。但是这些 $O (n^{2})$ 复杂度的排序方法太费时间了，我们可以将其转化成数组后再排序。

step 1：遍历链表，将节点值加入数组。
step 2：sort函数对数组进行排序。
step 3：依次遍历数组和链表，按照位置将链表中的节点值修改为排序后的数组值。

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        vector<int> nums; 
        ListNode* p = head;
        while(p != NULL){ //遍历链表，将节点值加入数组
            nums.push_back(p->val);
            p = p->next;
        }
        p = head;
        sort(nums.begin(), nums.end()); //对数组元素排序
        for(int i = 0; i < nums.size(); i++){ //遍历数组
            p->val = nums[i]; //将数组元素依次加入链表
            p = p->next;
        }
        return head;
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，sort函数的复杂度
空间复杂度： $O (n)$ ，存储链表元素值的辅助数组长度 $n$

方法二：归并排序

具体做法：

前面我们做合并两个有序链表不是使用归并思想吗？说明在链表中归并排序也不是不可能使用，合并阶段可以参照前面这道题，两个链表逐渐取最小的元素就可以了，但是划分阶段呢？

常规数组的归并排序，是将数组从中间个元素开始划分，然后将划分后的子数组作为一个要排序的数组，再将排好序的两个子数组合并成一个完整的有序数组，因此采用的是递归。而链表中我们也可以用同样的方式，只需要找到中间个元素的前一个节点，将其断开，就可以将链表分成两个子链表，然后继续划分，直到最小，然后往上依次合并。

step 1：首先判断链表为空或者只有一个元素，直接就是有序的。
step 2：准备三个指针，快指针right每次走两步，慢指针mid每次走一步，前序指针left每次跟在mid前一个位置。三个指针遍历链表，当快指针到达链表尾部的时候，慢指针mid刚好走了链表的一半，正好是中间位置。
step 3：从left位置将链表断开，刚好分成两个子问题开始递归。
- 终止条件： 当子链表划分到为空或者只剩一个节点时，不再继续划分，往上合并。
- 返回值： 每次返回两个排好序且合并好的子链表。
- 本级任务： 找到这个链表的中间节点，从前面断开，分为左右两个子链表，进入子问题排序。
step 4：将子问题得到的链表合并，参考合并两个有序链表。

归并具体过程可以参考如下图示：

alt

class Solution {
public:
    ListNode* merge(ListNode* pHead1, ListNode* pHead2) { //合并两段有序链表
        if(pHead1 == NULL) //一个已经为空了，直接返回另一个
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        ListNode* head = new ListNode(0); //加一个表头
        ListNode* cur = head;
        while(pHead1 && pHead2){ //两个链表都要不为空
            if(pHead1->val <= pHead2->val){ //取较小值的结点
                cur->next = pHead1;
                pHead1 = pHead1->next; //只移动取值的指针
            }else{
                cur->next = pHead2;
                pHead2 = pHead2->next; //只移动取值的指针
            }
            cur = cur->next; //指针后移
        }
        if(pHead1) //哪个链表还有剩，直接连在后面
            cur->next = pHead1;
        else
            cur->next = pHead2;
        return head->next; //返回值去掉表头
    }
    
    ListNode* sortInList(ListNode* head) {
        if(head == NULL || head->next == NULL) //链表为空或者只有一个元素，直接就是有序的
            return head;
        ListNode* left = head; 
        ListNode* mid = head->next;
        ListNode* right = head->next->next;
        while(right != NULL && right->next != NULL){ //右边的指针到达末尾时，中间的指针指向该段链表的中间
            left = left->next;
            mid = mid->next;
            right = right->next->next;
        }
        left->next = NULL; //左边指针指向左段的左右一个节点，从这里断开
        return merge(sortInList(head), sortInList(mid)); //分成两段排序，合并排好序的两段
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，归并排序的复杂度
空间复杂度： $O (l o g_{2} n)$ ，递归栈的深度最坏为 $l o g_{2} n$ 层