链表排序算法java实现（链表的快速排序、插入排序、归并排序）

左手的ㄟ右手 2022-05-09 05:54 260阅读 0赞

难易程度：★★

重要性：★★★

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

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;
            }

--------------------

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

![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240]

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

[1240]: /images/20220509/99c831b612fe4c199c68ab86937aaaaa.png