写了好久，终于写成了.第一次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); } }