单链表排序java_快速排序链表

单链表排序java_快速排序链表难易程度:★★重要性:★★★链表的排序相对数组的排序更为复杂些,也是考察求职者是否真正理解了排序算法(而不是“死记硬背”) 链表的插入排序 publicclassLinkedInsertSort{staticclassListNode{intval;ListNodenext;Lis…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

难易程度:★★

重要性:★★★

 

     链表的排序相对数组的排序更为复杂些,也是考察求职者是否真正理解了排序算法(而不是“死记硬背”)

  1. 链表的插入排序

    public  class LinkedInsertSort {
        static class ListNode {
            int val;
            ListNode next;
            ListNode(int x) {
                val = x;
                next = null;
            }
        }
    
        public static ListNode insertionSortList(ListNode head) {
            if(head==null||head.next==null)    return head;
    
            ListNode pre = head;//pre指向已经有序的节点
            ListNode cur = head.next;//cur指向待排序的节点
    
            ListNode aux = new ListNode(-1);//辅助节点
            aux.next = head;
    
            while(cur!=null){
                if(cur.val<pre.val){
                  //先把cur节点从当前链表中删除,然后再把cur节点插入到合适位置
                    pre.next = cur.next;
    
                    //从前往后找到l2.val>cur.val,然后把cur节点插入到l1和l2之间
                    ListNode l1 = aux;
                    ListNode l2 = aux.next;
                    while(cur.val>l2.val){
                        l1 = l2;
                        l2 = l2.next;
                    }
                    //把cur节点插入到l1和l2之间
                    l1.next = cur;
                    cur.next = l2;//插入合适位置
    
                    cur = pre.next;//指向下一个待处理节点
    
                }else{
                    pre = cur;
                    cur = cur.next;
                }
            }
            return aux.next;
        }
    }
  2. 链表的快速排序
    public static ListNode quickSort(ListNode begin, ListNode end) {
            //判断为空,判断是不是只有一个节点
            if (begin == null || end == null || begin == end)
                return begin;
            //从第一个节点和第一个节点的后面一个几点
            //begin指向的是当前遍历到的最后一个<= nMidValue的节点
            ListNode first = begin;
            ListNode second = begin.next;
    
            int nMidValue = begin.val;
            //结束条件,second到最后了
            while (second != end.next && second != null) {//结束条件
              //一直往后寻找<=nMidValue的节点,然后与fir的后继节点交换
                if (second.val < nMidValue) {
                    first = first.next;
                    //判断一下,避免后面的数比第一个数小,不用换的局面
                    if (first != second) {
                        int temp = first.val;
                        first.val = second.val;
                        second.val = temp;
                    }
                }
                second = second.next;
            }
            //判断,有些情况是不用换的,提升性能
            if (begin != first) {
                int temp = begin.val;
                begin.val = first.val;
                first.val = temp;
            }
            //前部分递归
            quickSort(begin, first);
            //后部分递归
            quickSort(first.next, end);
            return begin;
        }

     

  3. 链表的归并排序

    public ListNode mergeSort(ListNode head){
            if(head==null || head.next==null)    return head;
    
            ListNode mid = getMid(head);//获取链表中间节点
    
            //把链表从之间拆分为两个链表:head和second两个子链表
            ListNode second = mid.next;
            mid.next = null;
    
            //对两个子链表排序
            ListNode left = mergeSort(head);
            ListNode right = mergeSort(second);
    
            return merge(right,left);      
        }
    
        //两个有序链表的归并
        private ListNode merge(ListNode l1,ListNode l2){
          //辅助节点,排好序的节点将会链接到dummy后面
            ListNode dummy = new ListNode(0);
    
            ListNode tail = dummy;//tail指向最后一个排好序的节点
            while(l1!=null&&l2!=null){
                if(l1.val<=l2.val){
                    tail.next = l1;
                    l1 = l1.next;
                }else{
                    tail.next = l2;
                    l2 = l2.next;
                }
                tail = tail.next; //移动tail指针        
            }
    
            if(l1!=null)
                tail.next = l1;
            else
                tail.next = l2;
    
            return dummy.next;
    
        }
    
        //返回链表之间节点
        private ListNode getMid(ListNode head){
            if(head==null ||head.next==null)    return head;
    
            ListNode slow = head;
            ListNode faster = head.next;
            while(faster!=null&&faster.next!=null){
                slow = slow.next;
                faster = faster.next.next;
            }
            return slow;
        }

     


扫描下方二维码,及时获取更多互联网求职面经javapython爬虫大数据等技术,和海量资料分享
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务;
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料java面试考点java面经总结,以及几十个java、大数据项目资料很全,你想找的几乎都有

扫码关注,及时获取更多精彩内容。(博主今日头条大数据工程师)

扫码关注,及时获取更多精彩内容。(博主今日头条大数据工程师)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183359.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SpringBoot—–SpringBoot序列化Long转String「建议收藏」

    SpringBoot—–SpringBoot序列化Long转String「建议收藏」

  • tree命令安装

    tree命令安装linux下文件系统是目录树的形式存在,可以通过tree命令显示查看目录树结构。但是在linux系统上并没有tree这个命令,这里进行tree命令安装的讲述。安装tree命令:[root@lijinbutree-1.7.0]#tree-bash:tree:commandnotfound这表示tree命令没有安装。下载最新的tree命令源码压缩包:ftp://mama.inds

  • Java重载和重写的区别「建议收藏」

    Java重载和重写的区别「建议收藏」1、方法的重载的概念在同一个类中,允许存在一个以上的同名方法,只要同名的参数个数或者参数类型不同即可。总结:”两同一不同”:同一个类、相同方法名参数列表不同:参数个数不同,参数类型不同2、例构成重载的举例:不能构成重载的举例:3、如何判断是否构成方法的重载?严格按照定义判断:两同一不同跟方法的权限修饰符、返回值类型、形参变量名、方法体都没关系!4、如何确定类中某一个方法的调用:方法名——>参数列表子类继承父类以后,可以对父类中同名同参数的方法,进行覆盖操作重写以后,当创建子类对象以后,通过

  • java pojo 是什么_什么是POJO「建议收藏」

    java pojo 是什么_什么是POJO「建议收藏」POJO(PlainOldJavaObjects)简单的Java对象,实际就是普通JavaBeans,是为了避免和EJB混淆所创造的简称。在Java应用程序中的角色使用POJO名称是为了避免和EJB混淆起来,而且简称比较直接.其中有一些属性及其gettersetter方法的类,没有业务逻辑,有时可以作为VO(value-object)或dto(DataTransformObject)…

  • Java使用HttpURLConnection上传文件

    Java使用HttpURLConnection上传文件

  • 2022年编程语言排名,官方数据来了,让人大开眼界。「建议收藏」

    2022年编程语言排名,官方数据来了,让人大开眼界。「建议收藏」之所以说这件事,就是想告诉同学们,努力固然重要,但选择必须要对,一旦选择错了,那很多努力都是白费。这篇文章就是来给同学们提个醒,2022年最好的编程语言是什么?看完后你就知道该如何地去选择了。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号