【LeetCode-中等题】148. 排序链表

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等题】148. 排序链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

【LeetCode-中等题】148. 排序链表,力扣,# 中等题,leetcode,链表,windows

方法一:集合排序(核心是内部的排序)

把链表放到List集合,排好序,再依据List集合创建一个新有序链表返回就行了

//方法一 集合倒序  (存.val值在转换为ListNode)
    public ListNode sortList(ListNode head) {
        if(head == null) return head;
        List<Integer> list = new ArrayList<>();
        ListNode node = head;
        while(node != null){
            list.add(node.val);
            node = node.next;
        }
        Collections.sort(list);//升序排列
        ListNode min = new ListNode(list.get(0));//直接找出小值记录头结点
        node = min;
        for(int i = 1; i<list.size(); i++){
            ListNode h = new ListNode(list.get(i));
            node.next = h;
            node = node.next;
        }
        return min;
    }


// 方法一 集合倒序(存ListNode值直接调用Comparator接口进行值排序)
    //     public ListNode sortList(ListNode head) {
    //     if(head == null){
    //         return null;
    //     }
    //     List<ListNode> list  = new ArrayList<>();
    //     while(head !=null){
    //         list.add(head);
    //         head = head.next;
    //     }
    //     list.sort(new Comparator<ListNode>(){
    //         @Override
    //         public int compare(ListNode o1, ListNode o2) {
    //             return o1.val - o2.val;
    //         }
    //     });
    //     for(int i = 0 ; i < list.size() - 1;i++){
    //         list.get(i).next = list.get(i + 1);
    //     }
    //     list.get(list.size() - 1).next = null;
    //     return list.get(0);

方法二: 优先队列(核心也是内部的排序)

优先队列 往这个优先队列中插入元素时,会按照节点 val 属性的大小顺序进行排序,即小的节点排在前面,大的节点排在后面。依次谈栈再创建新链表
优先队列声明

PriorityQueue<ListNode> queue = new PriorityQueue<>((node1, node2) -> node1.val - node2.val);
  	((node1, node2) -> node1.val - node2.val)  升序排列
    ((node1, node2) -> node2.val - node1.val)  降序排列
 public ListNode sortList(ListNode head) {

        PriorityQueue<ListNode> queue = new PriorityQueue<>((node1, node2) -> node1.val - node2.val);

        ListNode cur = head;
        while (cur != null) {
            queue.offer(cur);
            cur = cur.next;
        }

        ListNode dummy = new ListNode(0);
        cur = dummy;
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }
        cur.next = null;

        return dummy.next;
    }

方法三:归并排序(带递归) 从上往下

先找到中间点 按中间点切割链表 然后排序好切割好的两头的链表 再将两个排序好的链表合并起来 (递归终止条件是切割到只有一个节点,直接返回可以排序了)

  1. 先找到待排序链表的中间节点(快慢指针找)
  2. 再根据中间节点对两边的链表分别进行归并排序(递归)
  3. 将排序好的两部分链表进行合并( 双指针法 无需递归)

【LeetCode-中等题】148. 排序链表,力扣,# 中等题,leetcode,链表,windows

         public ListNode sortList(ListNode head) {
                    return mergeSort(head);
        }
          // 归并排序
          private ListNode mergeSort(ListNode head){
                if(head ==null || head.next==null) return head;// 如果没有结点/只有一个结点,无需排序,直接返回--也是递归的出口
                // 快慢指针找出中位点
                ListNode fast = head.next;//让fast比slow快1个位置,这样最后solw会停在链表中间点前一个位置
                // ListNode fast = head.next.next;//两种方式都可以  最终slow都会停在中间点前一个位置
                ListNode slow = head;
                 //记住这个判断条件,偶数结点会找靠左结点,奇数就是中间节点,能用到很多题上
                while(fast !=null && fast.next !=null){
                    slow =slow.next;
                    fast = fast.next.next;
                }
                // 对右半部分进行归并排序
                ListNode right = mergeSort(slow.next);
                
                // 对左半部分进行断链操作
                slow.next =null;

                // 对左半部分进行归并排序
                ListNode left = mergeSort(head);

                //合并两个有序链表
                return mergeList(left,right);
    
          } 


           // 合并链表  双指针法
          private ListNode mergeList(ListNode l,ListNode r){
              // 临时头节点
              ListNode tmpHead=new ListNode(-1);

            ListNode tem = tmpHead;
            while( l!=null && r!=null ){  //只循环走到任何一方为null时  后面就不需要再比较了  直接把多的哪一方拼接起来就行
                if(l.val < r.val){
                    tem.next =l;
                    l = l.next;
                }else{
                    tem.next =r;
                    r = r.next;
                }
                tem = tem.next;
            }
            if(l==null) tem.next = r;//只循环走到任何一方为null时  后面就不需要再比较了  直接不为null的哪一方拼接起来就行
            else tem.next =l;
            return tmpHead.next;
          }

方法四:归并排序(省去递归,用迭代) 从下往上

核心就行直接定义排序的最小单位 也就是一个节点的链表(大for循环从intv = 1(子俩表长度) 开始 在intv >= 大链表的长度停止),然后分别对链表长度为1 2 3 4 进行合并排序,然后拼接到一起,就是排序号的链表

【LeetCode-中等题】148. 排序链表,力扣,# 中等题,leetcode,链表,windows文章来源地址https://www.toymoban.com/news/detail-680364.html

 public ListNode sortList(ListNode head) {
            if(head == null) return head;
            int length = 0;//统计链表的长度
            ListNode node = head;
            while(node != null){
                length++;
                node = node.next;
            }
            ListNode preHead = new ListNode(0,head);//创建哑结点  preHead--->head

            for(int intv = 1; intv < length ;intv=intv*2){ //每次intv扩大两倍   直到intv 大于等于了链表的长度
               ListNode prev = preHead;//prev为拼接点(拼接合并好的链表)
               ListNode cur = preHead.next;
               while(cur != null){//开始拆分
                 ListNode head1 = cur;//intv为1 时的 第一段链表的头节点
                 for(int i = 1 ; i<intv&&cur.next !=null&& cur != null;i++){//找到intv为1 时的 第一段链表的末尾节点  方便找到第二段的头结点 
                        cur=cur.next;//此时循环结束   cur指向的是第一段链表的尾部 
                 }
                  ListNode head2 = cur.next;//intv为1 时的 第二段链表的头节点
                  cur.next = null;  //端链操作  将两部分链表断开
                  cur = head2;  //更新cur到第二段链表的首节点


                  for(int i = 1 ; i<intv && cur != null  && cur.next != null ; i++){
                             cur=cur.next;//此时 cur指向的是第二段链表的尾部
                  }

                  ListNode next = null;
                 if(cur != null){  //记录第二次进行 比较的  第一段链表的第一个节点
                     next = cur.next;
                     cur.next = null;//对第一次比较的第二个链表进行断链
                 }

                 ListNode merged = mergeList(head1,head2);//对第一次的两个链表进行合并排序
                 prev.next = merged;//将合并好的链表 拼接到prev后面
                while(prev.next != null){
                    prev = prev.next; //把prev移动到拼接好的链表的尾部,方便下次再拼接合并排序好的链表
                }
                cur = next;//将cur更新到下一批次合并排序的第一个俩表的头结点

               }
            }
            return preHead.next;
    }

    //        // 合并两个有序链表  双指针法
          private ListNode mergeList(ListNode l,ListNode r){
               // 临时头节点
            ListNode tmpHead= new ListNode(-1);
            ListNode tem = tmpHead;
            while( l!=null && r!=null ){  //只循环走到任何一方为null时  后面就不需要再比较了  直接把多的哪一方拼接起来就行
                if(l.val < r.val){
                    tem.next =l;
                    l = l.next;
                }else{
                    tem.next =r;
                    r = r.next;
                }
                tem = tem.next;
            }
            if(l==null) tem.next = r;//只循环走到任何一方为null时  后面就不需要再比较了  直接不为null的哪一方拼接起来就行
            else tem.next =l;
            return tmpHead.next;
          }

到了这里,关于【LeetCode-中等题】148. 排序链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-中等题】24. 两两交换链表中的节点

    图解: 思路: 设置一个哑结点,作为第一次交换的落脚点 设置落脚点往后两个节点 执行交换,并且让后面的那个节点指向下一次交换的左节点 最后更新落脚点,进行下次循环, 一旦temp.next.next 或者 temp.next 为null,说明落脚点后面的节点不满足两两交换的条件

    2024年02月10日
    浏览(35)
  • LeetCode 92. Reverse Linked List II【链表,头插法】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(39)
  • LeetCode、2300. 咒语和药水的成功对数【中等,排序+二分】

    博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。 博主所有博客文件目录索引:博客目录索引(持续更新) 视频平台:

    2024年01月20日
    浏览(35)
  • LeetCode、2542. 最大子序列的分数【中等,排序+小顶堆】

    博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。 博主所有博客文件目录索引:博客目录索引(持续更新) 视频平台:

    2024年01月18日
    浏览(41)
  • 【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表

    剑指 Offer 36. 二叉搜索树与双向链表 后序遍历、二叉搜索树 二叉搜索树中的任一节点的 直接前驱为其左子树的最右侧节点,直接后继为其右子树的最左侧节点 。因此,可以通过这个关系来操作原来的二叉树。 为了不影响深度较大的节点的判断,使用后序遍历。 Step1. 后序遍

    2024年02月13日
    浏览(42)
  • 【LeetCode力扣】86. 分隔链表

      目录 1、题目介绍 2、解题思路 2.1、双链表双指针 2.2、代码描述   原题链接: 86. 分隔链表 - 力扣(LeetCode)   示例 1: 输入: head = [1,4,3,2,5,2], x = 3 输出: [1,2,2,4,3,5]   示例 2: 输入: head = [2,1], x = 2 输出: [1,2]   提示: 链表中节点的数目在范围 [0, 200] 内 -100 = Node.val

    2024年02月08日
    浏览(31)
  • LeetCode 138. Copy List with Random Pointer【链表,DFS,迭代,哈希表】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(37)
  • 【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表

      目录 1、题目介绍 2、解题思路 2.1、暴力破解法 2.2、快慢指针反转链表   原题链接:  234. 回文链表 - 力扣(LeetCode) 示例 1: 输入: head = [1,2,2,1] 输出: true  示例 2: 输入: head = [1,2] 输出: false  提示:  链表中节点数目在范围[1, 10^5] 内 0 = Node.val = 9 进阶: 你能否用

    2024年02月08日
    浏览(43)
  • day19【LeetCode力扣】160.相交链表

    1.题目描述 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交**:** 题目数据 保证 整个链式结构中不存在环。 注意 ,函数返回结果后,链表必须 保持其原始结构

    2024年01月18日
    浏览(38)
  • 力扣每日一道系列 --- LeetCode 160. 相交链表

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 160. 相交链表 思路: 首先计算两个链表的长度,然后判断两个链表的尾节点是否相同。如果不同,那么这两个链表就没有交集,返回空;如果相同,那么就

    2024年02月05日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包