当前位置:首页 » 《资源分享》 » 正文

链表的排序_ 落禅的博客

6 人参与  2021年10月04日 16:43  分类 : 《资源分享》  评论

点击全文阅读


148. 排序链表

你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

进阶:

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

示例 1:

image-20210911105926649

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

image-20210911105945165

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

链表排序的最佳方法:归并排序

1.找到中间节点

2.将中间节点断成左右两半,然后再次递归找到中间节点,再次进行分割,直到最后分割成一个一个的单个元素

3.然后两两排序,之后四四排序…直到最后将整张链表排成一个有序链表

这个思想和归并排序一样,归并排序的原理也是将数据分割成小部分,然后每一个小部分进行排序,让局部有序,然后整体有序

class Solution {
public:
//链表的排序:归并排序
//1.找到中间节点
//2.将链表分为两部分
//3.实现有序链表的排序
    ListNode*Sort(ListNode*&l,ListNode*&r)
    {
    //到这里就是排序的思想了,排序思想和合并两个有序链表的思想差不多
    //创建新的节点,然后按照插入排序的思想,谁大谁就插入
    //如果这边有点问题的话可以去看看合并两个有序链表
        ListNode*dummyHead=new ListNode(0);
        ListNode*cur=dummyHead;
        while(l!=nullptr&&r!=nullptr)
        {
            if(l->val<=r->val)
            {
                cur->next=l;
                cur=cur->next;
                l=l->next;
            }
            else
            {
                cur->next=r;
                cur=cur->next;
                r=r->next;
            }
        }
        if(l!=nullptr)
        {
            cur->next=l;
        }
        if(r!=nullptr)
        {
            cur->next=r;
        }
        return dummyHead->next;
    }
    //传递参数时记得引用传递
    ListNode*MergSort(ListNode*&head)
    {
    //判断头节点的下一个节点是否为空,如果是,直接返回头节点
        if(head->next==nullptr)
        return head;
        //定义快慢指针,寻找中间节点
        ListNode*slow=head;
        ListNode*fast=head;
        ListNode*prev=nullptr;
        while(fast&&fast->next)
        {
            prev=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        //此时slow所在的位置就是中间节点所在的位置,prev指向slow的前一个节点
        //我们人为的让链表从slow这个地方断开,head->prev是链表的前半段,slow到完是链表的右半部分
        prev->next=nullptr;
		//递归在左、右两端继续找中间节点
        ListNode*l=MergSort(head);
        ListNode*r=MergSort(slow);
        //当分割的不能分割时,进行排序,最开始两两排序,到后来四四排序
        return Sort(l,r);
    }
    ListNode* sortList(ListNode* head) {
    //1.判断节点是否为空
        if(head==nullptr)
        return head;
        //2.进入归并排序,寻找中间节点
        return MergSort(head);

    }
};

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/29385.html

排序  节点  链表  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 从市府大秘到权力巅峰读者推荐_陆一鸣凌思文后续+完结_小说后续在线阅读_无删减免费完结_
  • 周晚黎厉北辰小说(死后我弃夫虐茶,独美不原谅)(周晚黎厉北辰)全书+后续+结局在线阅读
  • 小说大结局小说山与星辰小说已更新+特别篇(林景山苏星辰)纯净版
  • 终章小说顾澜音封灼年完结篇(碑婚)已更新+延伸(顾澜音封灼年)清爽版
  • 宋予柯奕烜小说小说全集+延伸+完本(玩笑沦陷)畅享在线阅读
  • 宋璃陆泽野小说(七零大院:离婚后嫁绝嗣京少多胎)小说结尾+隐藏篇章(宋璃陆泽野)畅享阅读
  • 完结文重生后我让校花保管所有准考证完结+结局+番外宝藏美文列表_完结文重生后我让校花保管所有准考证完结+结局+番外宝藏美文(秦雨然江述怀洛瑶)
  • 重生在高考前,我笑着送小青梅和小混混去庆祝成人礼一口气读完乔念沈晏安陆坤完本_重生在高考前,我笑着送小青梅和小混混去庆祝成人礼一口气读完(乔念沈晏安陆坤)
  • 此后锦书休寄免费品鉴(阮时苒厉寒霆),此后锦书休寄免费品鉴
  • 高分_玩笑沦陷小说(宋予柯奕烜)(玩笑沦陷)全本完整阅读
  • 离婚后,假千金她成了万人迷是什么小说(江浸月陆明渊)(离婚后,假千金她成了万人迷)全本完整清爽版在线+无广告结局
  • 晚晚的重生回到全家被杀的除夕夜+整本林炎晚晚全书在线

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1