题解 | #单链表的排序#

题目的主要信息：

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM5.合并k个已排序的链表

BM20.数组中的逆序对

方法一：归并排序（推荐使用）

知识点1：分治

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。

知识点2：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

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

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

• 终止条件： 当子链表划分到为空或者只剩一个节点时，不再继续划分，往上合并。
• 返回值： 每次返回两个排好序且合并好的子链表。
• 本级任务： 找到这个链表的中间节点，从前面断开，分为左右两个子链表，进入子问题排序。

怎么找中间元素呢？我们也可以使用快慢双指针，快指针每次两步，慢指针每次一步，那么快指针到达链表尾的时候，慢指针正好走了快指针距离的一半，为中间元素。

具体做法：

• step 1：首先判断链表为空或者只有一个元素，直接就是有序的。
• step 2：准备三个指针，快指针right每次走两步，慢指针mid每次走一步，前序指针left每次跟在mid前一个位置。三个指针遍历链表，当快指针到达链表尾部的时候，慢指针mid刚好走了链表的一半，正好是中间位置。
• step 3：从left位置将链表断开，刚好分成两个子问题开始递归。
• step 4：将子问题得到的链表合并，参考合并两个有序链表。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    //合并两段有序链表
    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 != null && pHead2 != null){ 
            //取较小值的节点
            if(pHead1.val <= pHead2.val){ 
                cur.next = pHead1;
                //只移动取值的指针
                pHead1 = pHead1.next; 
            }else{
                cur.next = pHead2;
                //只移动取值的指针
                pHead2 = pHead2.next; 
            }
            //指针后移
            cur = cur.next; 
        }
        //哪个链表还有剩，直接连在后面
        if(pHead1 != null) 
            cur.next = pHead1;
        else
            cur.next = pHead2;
        //返回值去掉表头
        return head.next; 
    }
    
    public 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)); 
    }
}

C++实现代码：

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

Python代码实现：

class Solution:
    #合并两段有序链表
    def merge(self, pHead1:ListNode, pHead2:ListNode) : 
        #一个已经为空了，直接返回另一个
        if pHead1 == None: 
            return pHead2
        if pHead2 == None:
            return pHead1
        #加一个表头
        head = ListNode(0) 
        cur = head
        #两个链表都要不为空
        while pHead1 and 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 
    
    def sortInList(self , head ):
        #链表为空或者只有一个元素，直接就是有序的
        if head == None or head.next == None: 
            return head
        left = head
        mid = head.next
        right = head.next.next
        #右边的指针到达末尾时，中间的指针指向该段链表的中间
        while right and right.next:
            left = left.next
            mid = mid.next
            right = right.next.next
        #左边指针指向左段的左右一个节点，从这里断开
        left.next = None 
        #分成两段排序，合并排好序的两段
        return self.merge(self.sortInList(head), self.sortInList(mid)) 

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，每级划分最坏需要遍历链表全部元素，因此为$O(n)O(n)$，每级合并都是将同级的子问题链表遍历合并，因此也为$O(n)O(n)$，分治划分为二叉树型，一共有$O(lo{g}_{2}n)O(log\_2n)$层，因此复杂度为$O((n+n)\ast lo{g}_{2}n)=O(nlo{g}_{2}n)O((n+n)*log\_2n)=O(nlog\_2n)$
• 空间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，递归栈的深度最坏为树型递归的深度，$lo{g}_{2}nlog\_2n$层

方法二：转化为数组排序（扩展思路）

思路：

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

具体做法：

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

Java实现代码：

import java.util.*;
public class Solution {
    public ListNode sortInList (ListNode head) {
        ArrayList<Integer> nums = new ArrayList(); 
        ListNode p = head;
        //遍历链表，将节点值加入数组
        while(p != null){ 
            nums.add(p.val);
            p = p.next;
        }
        p = head;
        //对数组元素排序
        Collections.sort(nums); 
        //遍历数组
        for(int i = 0; i < nums.size(); i++){ 
            //将数组元素依次加入链表
            p.val = nums.get(i); 
            p = p.next;
        }
        return head;
    }
}

C++实现代码：

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

Python实现代码：

class Solution:
    def sortInList(self , head ):
        p = head
        nums = []
        #遍历链表，将节点值加入数组
        while p: 
            nums.append(p.val)
            p = p.next
        p = head
        #对数组元素排序
        nums.sort() 
        #遍历数组
        for i in range(len(nums)): 
            #将数组元素依次加入链表
            p.val = nums[i] 
            p = p.next
        return head

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort函数一般为优化后的快速排序，复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$
• 空间复杂度：$O(n)O(n)$，存储链表元素值的辅助数组长度$nn$