归并排序，如果不要求O(1)的空间复杂度，可以很简洁的完成：
找到当前链表的中点，然后对链表的两半递归的进行排序，merge
但是现在需要O(1)的空间，所以不能递归，选用自底向上的归并排序：
对原链表按不同的粒度进行划分，一开始粒度为1，然后进行merge
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { // bottom up的排序 // cut:在第n个节点处断开，返回之后链表 private ListNode cut(ListNode head,int n){ ListNode p=head; while(n>1&&p!=null){ n--; p=p.next; } if(p==null){ return null; } ListNode t=p.next; p.next=null; return t; } private ListNode merge(ListNode a,ListNode b){ // 尾插法即可 ListNode dummy=new ListNode(0); ListNode t=dummy; while(a!=null&&b!=null){ if(a.val<b.val){ t.next=a; t=a; a=a.next; }else{ t.next=b; t=b; b=b.next; } } if(a!=null){ t.next=a; } if(b!=null){ t.next=b; } return dummy.next; } public ListNode sortList(ListNode head) { int len=0; ListNode p=head; while(p!=null){ p=p.next; len++; } ListNode dummy=new ListNode(0); dummy.next=head; for(int sz=1;sz<len;sz=sz*2){ ListNode t=dummy; p=dummy.next; while(p!=null){ ListNode a=p; p=cut(p,sz); ListNode b=p; p=cut(p,sz); t.next=merge(a,b); while(t.next!=null){ t=t.next; } } } return dummy.next; } }注意cut中要注意对空指针的检查
