您现在的位置是:首页 > 正文

LeetCode148.排序链表

2024-01-30 20:00:14阅读 0

看完题目的想法是,直接把所有节点的值都遍历出来放进优先队列里面,然后从头节点遍历一次,每次把优先队列poll()的值赋给节点的val即可,说实话,想完还觉得估计有问题怎么可能这么简单,但是不管了,5分钟就把这个算法写出来了,一提交,居然通过了!以下是我的代码:

class Solution {
    public ListNode sortList(ListNode head) {

        PriorityQueue<Integer> pri = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer e1, Integer e2){
                  return e1 - e2;
            }
        });

      ListNode h = head;
      while(h != null){
          pri.add(h.val);
          h = h.next;
      }
      ListNode h2 = head;
      while(h2 != null){
          h2.val = pri.poll();
          h2 = h2.next;
      }
      
     return head;

    }

其实这个优先队列也不用new一个比较器实例,因为默认是从小到大的。然后看看官方题解吧,不要用我这种二流子写法了。

题解用的是归并排序,先把链表分成两半,每半分别排序,然后再把排完序的两半合并起来;对于两半中的每一半也是这样的,把这半再分成两半,两半分别排好序合起来,只有当“一半”只有两个节点是不用再分,直接比较这两个节点然后排序,然后再与另一半合起来,然后再与更大的另一半合起来...一直合到这个完整的最大的链表。

分割可以采用快慢指针的方法,快慢指针同时从头节点出发,快指针每次走两步,慢指针每次走一步,当快指针到达链尾,慢指针就在中间节点。然后利用递归的方法不断的分割链表,直到只剩两个节点,开始合并。

合并先创建一个哑节点,然后分别比较左右两个链表的头节点,最小的先移到哑节点后面,然后这个链表的指针移到下一个节点,下次比较就是这个链表的第2个节点和另一个链表的第一个节点,(因为两个链表都是已经排好序的,所以每次只要比较两个链表未放进去的最小节点即可),如果一个链表已经遍历完了,只要把另一个链表剩下的部分直接挂在后面即可。

以下是题解代码:

class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

网站文章

  • Markdown语法之段落与换行

    Markdown语法之段落与换行

    Markdown语法之段落与换行 没有空行 我是第一行 我是第二行 有空行 我是第一行 我是第二行 段内换行 我是第一行,如果想段内换行需要在结尾插入两个以上的空格 我是第二行...

    2024-01-30 20:00:07
  • Mybatis源码解析(四) —— SqlSession是如何实现数据库操作的?

    Mybatis源码解析(四) —— SqlSession是如何实现数据库操作的?

    Mybatis源码解析(四) —— SqlSession是如何实现数据库操作的?  如果拿一次数据库请求操作做比喻,那么前面3篇文章就是在做请求准备,真正执行操作的是本篇文章要讲述的内容。正如标题一样,本篇文章最最核心的要点就是 SqlSession实现数据库操作的源码解析。但按照惯例,我这边依然列出如下的问题:1、 SqlSession 是如何被创建的? 每次的数据库操...

    2024-01-30 19:59:39
  • Java基础之comparator和comparable的区别以及使用

    Java基础之comparator和comparable的区别以及使用1: 区别:1、Comparable类需要实现此接口,定义在类内,不利于扩展2 、Comparator更灵活,可以随时自定义比较规则 使用: 2.2、 Collections.sort(List<T> list,Comparator<? super T> ...

    2024-01-30 19:59:31
  • 《制造业数据建设白皮书》

    《制造业数据建设白皮书》

    如何提高柔性生产水平、科学敏捷决策,在波动不定的市场环境中始终保留自己的一席之地,是制造企业需要持续关注的问题,也成为了每一个制造行业企业主的必然“大考”。制造行业是立国之本与强国之基,以数字经济发展...

    2024-01-30 19:59:23
  • matplotlib:添加引导线及多组数据直方图

    matplotlib:添加引导线及多组数据直方图

    2024-01-30 19:58:55
  • Vue学习过程中的坑

    Vue学习过程中的坑

    1.在创建组件时报错Invalid value for option "components": expected an Object, but got Array在注册组件时,components:{},而非components:[],解决办法:components:{ template}学习博客:https://blog.csdn.net/zhongg...

    2024-01-30 19:58:47
  • 《Linux私房菜》——二、BASH以及相关命令(变量、配置文件、数据流定向、pipe、sort、选取命令等)

    本文来自《鸟哥的Linux私房菜》学习以及知识点整理,仅供学习使用文章目录一、查看系统合法的shell二、bash的优点历史命令文件补全别名三、查看命令类型type四、命令执行、删除快捷键五、变量5....

    2024-01-30 19:58:39
  • Android Jetpack Compose —— 控件 最新发布

    上一篇文章已经介绍了Android Jetpack Compose,相信都知道了compose是以kotlin为主,在学习前可以先了解一些compose控件。这一章主要是介绍常用的控件,这些控件在使用的时候是必不可少的,这个需要我们慢慢练习,才能达到孰能生巧。

    2024-01-30 19:58:32
  • CS231n-assignment1详解

    CS231n-assignment1详解

    博客中的一部分公式和图片无法展示,建议移步至GitHub中。assignment1中有一个assignment.pdf,这个就是本文导出的pdf版本。 Github传送门 1. 配置问题 考虑到很多朋...

    2024-01-30 19:58:02
  • Python基础

    Python基础

    目录1、IPO编程2、Python的两种编程方式3、Python语法1、注释2、命名和保留字3、数据类型4、字符串的使用5、分支语句6、print()的格式化1、IPO编程I:input程序输入P:process处理O:output输出2、Python的两种编程方式交互式和文件式交互式:对每个输入语句即时运行结果,适合语法练习文件...

    2024-01-30 19:57:54