首页 > 代码库 > leecode 归并排序 链表(java)

leecode 归并排序 链表(java)

2024-07-08 04:08:16   217人阅读

写了好久，终于写成了.第一次zai leecode错题，题目质量很高，适合面试，与

1.归并排序是稳定的，在java中 Arrays.sort(a);中对于对象的排序就是归并排序。对于原子类型数据使用的是快排。

2.算法复杂度，我们都知道归并排序的最好最坏最差复杂度为nlogn，空间复杂度为n，在链表当中，空间复杂度j降为O(1)。

3.写链表的排序

1.分： 使用书上的快慢指针来获得中间节点，分割成2个链表

2.和： 将两个链表合成一个，比较简单

3.

主程序

ListNode lmerge(ListNode list)

{

if(list==null)  return  null;//如果是空链表

if(list.next==null) return list;//单个节点

//以下是多节点的情况

1分割 返回中间的地址   middle=split(head)

return (middle,head); 、、 返回连接后的地址

 

 

}

package LinkedListSort;class ListNode {        int val;        ListNode next;        ListNode(int x) {            val = x;            next = null;        }     }public class LinklistSort {        public static ListNode create(int a[])    {      ListNode head=new ListNode(a[0]);      for(int i=1;i<a.length ;i++)      {          ListNode node=new ListNode(a[i]);          node.next=head.next;          head.next=node;                                    }      return head;                    }    public static void display(ListNode head)    {        ListNode list=head;        while(list!=null)        {                        System.out.print(list.val+"--");            list=list.next;                    }        System.out.println();                    }       public static ListNode sortList(ListNode head) {       //没有一个节点       if(head==null) return null;       //有一个节点       if(head.next==null) return head;         //有两个以上的节点                   ListNode middle=split(head);             return merge(sortList(head),sortList(middle));                                     }    private static ListNode merge(ListNode head, ListNode middle) {            ListNode p1=head;        ListNode p2=middle;        ListNode h=new ListNode(-1);//一个new头        ListNode tail=h;                while(p1!=null&&p2!=null)        {            if(p1.val<=p2.val)            {                                tail.next=p1;                tail=tail.next;                p1=p1.next;                                                            }            else            {                tail.next=p2;                tail=tail.next;                                p2=p2.next;                            }                                            }            if(p1!=null)        {            tail.next=p1;                    }        if(p2!=null)        {            tail.next=p2;        }                return h.next ;}    //分成两部分的部分    private static ListNode split(ListNode head) {        ListNode quick=head;        ListNode slow=head;        ListNode pre=null;        while(quick!=null)        {            pre=slow;            slow=slow.next;            quick=quick.next;            if(quick!=null) quick=quick.next ;                                                            }        pre.next =null;    return slow;}    public static void main(String[] args) {        // TODO Auto-generated method stub        int a[]={1,3,-5,8,56,44,56};         ListNode list=create(a);        // display(list);         ListNode l=sortList(list);                 display(l);                     }}


联系
我们