链表的特点决定了只能从前往后的遍历，我的第一个思路是冒泡排序，但是超时，看了一眼归并排序的写法，真的是妙啊。

1 冒泡（未通过）

    public ListNode sortInList (ListNode head) {
        // write code here
        ListNode res=null;
        if(head==null){
            return res;
        }
        int nodeNum=0;
        ListNode p=head;
        while(p!=null){ //遍历链表获得链表节点数，节点数是用来控制沉降次数，9个节点，沉降8次
            nodeNum++;
            p=p.next;
        }
        for(int i=nodeNum-1;i>0;i--){
            int count=i; //控制这一次沉降的结束边界，后面的就不用沉降了已经是有序了
            ListNode p1=head;
            ListNode p2=head.next;
            while(count>0){
                if(p1.val>p2.val){//值交换
                    int tmp=p1.val;
                    p1.val=p2.val;
                    p2.val=tmp;
                }
                p1=p1.next;
                p2=p2.next;
                count--;
            }
        }
        res=head;
        return res;
    }

2 归并排序

public ListNode sortInList (ListNode head) {
    // write code here
    ListNode res=null;
    if(head==null){
        return res;
    }
    return mergeSort(head);
}
public ListNode mergeSort(ListNode head){
    if(head==null || head.next==null){ //最后没有节点或者最后还有一个节点，返回本身，一个节点本身就是有序了，不用排了
        return head;
    }
    ListNode slow=head;
    ListNode fast=head.next.next; //上面已经排除了1个节点的请情况，所以这里至少有两个节点，head.next.next 存在
    ListNode head1=head;
    while(fast!=null && fast.next!=null){ //两个节点不用进去循环，假如我们让进去循环的话，fast为null，fast.next 作为条件就报错。
        slow=slow.next;
        fast=fast.next.next;
    }
    ListNode head2=slow.next; //先保存后面链表的头节点
    slow.next=null;//将前面链表断开形成真正的两条链表
    ListNode left=mergeSort(head1);
    ListNode right=mergeSort(head2);
    return mergeList(left,right);
}
public ListNode mergeList(ListNode l1,ListNode l2 ){//这里比较巧妙，这是一个针对有序链表的写法，但是我们的拆分明明是不能保证有序的，哈哈，巧在当我们在不停的分治的过程中，最后一定是有单节点的合并的，两个单节点可以认为就是两个有序的链表，两个单节点的合并就是两个有序链表的合并，也就是说两个单节点链表合并成了一个拥有两个节点的有序链表，再继续向上回溯，从下网上就形成了两个有序链表的合并了。
    ListNode node=new ListNode(0);
    ListNode p=node;
    while(l1!=null||l2!=null){
        if(l1!=null && l2!=null){
            if(l1.val<l2.val){
                p.next=l1;
                l1=l1.next;
                p=p.next;
            }else{
                p.next=l2;
                l2=l2.next;
                p=p.next;
            }
        }else if(l1==null){
                p.next=l2;
                l2=l2.next;
                p=p.next;
        }else if(l2==null){
                p.next=l1;
                l1=l1.next;
                p=p.next;
        }
    }
    return node.next;
}