牛客题解官

2022-04-22 11:33 清华大学 Java

关注

题解 | #单链表的排序#

单链表的排序

http://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08

题目的主要信息：

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

举一反三：

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

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

BM20.数组中的逆序对

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

知识点1：分治

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

知识点2：双指针

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

思路：

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

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

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

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

具体做法：

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

图示：

alt

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 (n l o g_{2} n)$ ，每级划分最坏需要遍历链表全部元素，因此为 $O (n)$ ，每级合并都是将同级的子问题链表遍历合并，因此也为 $O (n)$ ，分治划分为二叉树型，一共有 $O (l o g_{2} n)$ 层，因此复杂度为 $O ((n + n) * l o g_{2} n) = O (n l o g_{2} n)$
空间复杂度： $O (l o g_{2} n)$ ，递归栈的深度最坏为树型递归的深度， $l o g_{2} n$ 层

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

思路：

链表最难受的就是不能按照下标访问，只能逐个遍历，那像排序中常规的快速排序、堆排序都不能用了，只能用依次遍历的冒泡排序、选择排序这些。但是这些 $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 (n l o g_{2} n)$ ，sort函数一般为优化后的快速排序，复杂度为 $O (n l o g_{2} n)$
空间复杂度： $O (n)$ ，存储链表元素值的辅助数组长度 $n$

全部评论

推荐最新楼层

玛隆

门头沟学院 Java

return head;这部分是对p进行排序，为什么返回head,可以解答下嘛，谢谢啦

1 回复分享

发布于 2022-07-08 11:53

我叫李舜生

中国石油大学（北京） C++

我才疏学浅，这里第二种方法直接改了每个节点指向的数值在实际过程中是不是不太好的习惯啊？万一传进来的链表在其他的地方还要用，那可乱套了。。。至少保证每个节点对应的数值不能变吧。

点赞回复分享

发布于 2022-12-21 11:20 北京

elpsycongroo_

武汉大学算法工程师

方法一java实现第45行代码中，为什么循环判断条件是"right != null && right.next != null"啊，我只写了right.next != null它报错，如果right指向不为空的话，那right节点本身肯定也不为空吧

点赞回复分享

发布于 2023-02-28 15:30 浙江

遥望五道口

算法工程师

哪位大佬能够解释一下，我在这里有点困惑这里添加了表头 ListNode* head = new ListNode(0); 返回时 //返回值去掉表头 return head->next; 那new出来的new ListNode(0)这一块空间不会造成内存泄漏吗，

点赞回复分享

发布于 2023-05-30 17:50 河北

牛客594267898号

香港中文大学（深圳） C++

直接用sort是不是有点作弊了

点赞回复分享

发布于 03-24 16:22 广东

11-22 00:40

美团_后端开发(准入职员工)

忙完了工作，又要毕业论文……

工作基本定了，比较满意。这深度学习真是难搞啊，论文看不懂，代码看不懂，不会改，创新点？？？ 还有一个月中期，怎么搞，已经抑郁了，没有小论文要求，我真是非常幸运了，不然就我这科研能力………… 感觉自己对自己失去信心，无时无刻不在否定自己取得一些成绩都是运气好罢了，真的能顺利毕业吗？严重内耗、无力感爆棚啊…………

AI牛可乐：哎呀，听起来你最近压力好大呀，毕业论文和工作的双重压力一定让你感觉像是背了两座山呢。深度学习确实挺复杂的，就像是要在一片迷雾中找到出路一样。但是，你已经很棒了，工作都定好了，这是很大的成就呢！论文的事情，别太担心。每个人都有看不懂代码和论文的时候，这是正常的。至于创新点嘛，有时候灵感就像小猫一样，需要一点一点地哄出来的。你可以先试试把你看过的资料整理一下，说不定就能找到新的思路呢。中期答辩前，你可以列个计划，一步一步来，把大问题分解成小问题，一点一点克服。记得，你不是一个人在战斗，你的导师、同学都是你的战友哦。至于信心嘛，别否定自己，每个人都会有低谷的时候。你已经取得的成绩，都是你实力的体现。毕业不是问题，只要你不放弃，就一定能顺利走过去的。加油哦，我相信你可以的！对了，如果你愿意的话，可以点击我的头像，我们私信聊，也许我能帮你出出主意，或者就是简单地聊聊天，分散一下你的注意力也好呀。🐮💪🌟

你们的毕业论文什么进度了牛客解忧铺

点赞评论收藏