java链表排序方法_java链表排序

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

Jetbrains全系列IDE稳定放心使用

插入排序

   对链表进行插入排序，是最简单的一种链表排序算法，用于插入排序是迭代的，所以每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
   每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。
   插入排序的时间复杂度为O(N^2)，空间复杂度为O（1）

class Solution { 
   
    public ListNode insertionSortList(ListNode head) { 
   
             ListNode move=head;
             ListNode emptyHead=new ListNode();
             emptyHead.next=head;
             while(move!=null&&move.next!=null){ 
   
                 if(!reInsert(move,emptyHead)) 
                     move=move.next;
             }
             return emptyHead.next;
    }
    private Boolean reInsert(ListNode node,ListNode emptyHead){ 
   
        ListNode temp=node.next;
        node.next=temp.next;
        while(emptyHead!= node){ 
   
            if(temp.val<=emptyHead.next.val){ 
   
                temp.next=emptyHead.next;
                emptyHead.next=temp;
                return true;
            }
            emptyHead=emptyHead.next;
        }
        temp.next=node.next;
        node.next=temp;
        return false;
    }
}

归并排序

   对于归并排序排序在数组排序中的运用，详细请点击此处。这里主要介绍归并排序在链表排序中的运用。
   在使用归并排序算法进行链表排序时，其基本思想是将链表细分成一个个子链表，将子链表进行排序，然后再将相邻的两个有序子链表进行合并，得到更长的有序链表，最后一步步得到整个有序链表，子链表进行合并排序时需要用到合并两个有序链表算法。
   归并链表排序的实现方式一共有两种，递归实现和非递归实现，两种实现方式的时间复杂度都是O(nlogn），但是由于递归实现调用函数时需要消耗大量栈空间，所以递归调用的空间复杂度是O（logn）。对于非递归调用，空间复杂度就是O（1）。

递归代码：

class Solution { 
   
    public ListNode sortList(ListNode head) { 
   
        if(head==null)
          return head;
       return mergeSort(head);
    }
    public ListNode mergeSort(ListNode head){ 
   
        if(head.next==null)
            return head;
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){ 
   
            fast=fast.next.next;
            if(fast!=null)
            slow=slow.next;
        }
        ListNode tempHead=slow.next;
        slow.next=null;
        ListNode left=mergeSort(head);
        ListNode right=mergeSort(tempHead);
        head=mergeList(left,right);
        return head;
    }
    public ListNode mergeList(ListNode head,ListNode tempHead){ 
   
        ListNode emptyHead=new ListNode(0,head);
        ListNode move=emptyHead;
        while(head!=null&&tempHead!=null){ 
   
            if(head.val<= tempHead.val){ 
   
                move.next=head;
                head=head.next;
            }else{ 
   
                move.next=tempHead;
                tempHead=tempHead.next;
            }
            move=move.next;
        }
        move.next=head==null?tempHead:head;
        return emptyHead.next;
    }
}

非递归代码：

class Solution { 
   
    public ListNode sortList(ListNode head) { 
   
        if(head==null)
            return null;
        ListNode end=head;
        int length=0;
        while(end!=null){ 
   
            length++;
            end=end.next;
        }
        ListNode emptyHead = new ListNode(0, head);
        for(int i=1;i<length;i<<=1){ 
   
            ListNode prev = emptyHead;
            ListNode cur = emptyHead.next;
            while(cur!=null) { 
   
                ListNode start1 =cur;
                for (int j = 1; j < i&&cur.next!=null; j++) { 
   
                    cur = cur.next;
                }
                ListNode start2 = cur.next;
                cur.next = null;
                cur = start2;
                for (int j = 1; j < i && cur != null&&cur.next!=null; j++) { 
   
                    cur = cur.next;
                }
                if(cur!=null){ 
   
                ListNode temp=cur;
                cur=cur.next;
                temp.next=null;
                }
                prev.next = mergeList(start1, start2);
                while(prev.next!=null){ 
   
                    prev=prev.next;
                }
            }
        }
        return emptyHead.next;
    }
    public ListNode mergeList(ListNode head,ListNode tempHead){ 
   
        ListNode emptyHead=new ListNode(0,head);
        ListNode move=emptyHead;
        while(head!=null&&tempHead!=null){ 
   
            if(head.val<= tempHead.val){ 
   
                move.next=head;
                head=head.next;
            }else{ 
   
                move.next=tempHead;
                tempHead=tempHead.next;
            }
            move=move.next;
        }
        move.next=head==null?tempHead:head;
        return emptyHead.next;
    }
}