单链表的排序

采用归并排序的方法。 注意递归时的终止条件为head==null||head.next==null; 首先通过快慢指针（首先让快指针先走一个），找到中点。 从中点分开进行归并，即 ListNode left=sortInList(head); ListNode right=sortInList(tmp); 之后new一个头节点拼接剩下的结点 最后判定一下是否还有剩下的节点进行拼接即可。

public ListNode sortInList (ListNode head) {
        // write code here
         if(head==null||head.next==null) return head;
        ListNode fast=head.next;
        ListNode slow=head;

        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode tmp=slow.next;
        slow.next=null;
        ListNode left=sortInList(head);
        ListNode right=sortInList(tmp);

        ListNode h=new ListNode(0);
        ListNode h0=h;
        while (left!=null&&right!=null){
            if(left.val< right.val){
                h0.next=left;
                left=left.next;
            }else {
                h0.next=right;
                right=right.next;
            }
            h0=h0.next;
        }
        h0.next=left!=null?left:right;
        return h.next;
    }