1、选择排序，外层循环定位起点，默认为最小值，内层循环一直找后面比当前起点小的值进行交换

注：其实这样做是不好的做法，因为题目的意思是想涉及节点的交换而不是单纯的值交换，但是这样结果也是对的，属于取巧了 
   public ListNode sortInList (ListNode head) {
        // write code here
        ListNode pre = head;
        while(pre!=null){
            ListNode preNext = pre.next;
            while(preNext!=null){
                if(pre.val>preNext.val){
                    int temp = pre.val;
                    pre.val=preNext.val;
                    preNext.val=temp;
                }
                preNext=preNext.next;
            }
            pre=pre.next;
        }
        return head;
    }

2、自底向上归并排序（时间复杂度（nlogn），空间复杂度O（logn))
将链表挨个分组，再（有序链表）合并，分组的办法是用快慢指针，当快指针走到末尾的时候，慢指针正好是一半的位置 
   public ListNode sortInList (ListNode head) {
    //这种情况出现那么就证明当前分组为单个的，那么不需要继续分组了 
       if(head.next==null){
           return head;
       } 
       //慢指针
       ListNode slow = head;
       //快指针，这里为什么不是head呢？而是head.next呢，
       ListNode fast = head.next;
        
        //如果head
// 假设 1，2，3，这样的情况，按照下面的while循环，slow落在2上没问题
// 假设 1，2这样的情况，slow落在2上，那如果要正常分组，slow应该落在1上
       //如果head.next
// 假设 1，2，3，这样的情况，按照下面的while循环，slow落在2上没问题,solw落在2上
// 假设 1，2这种情况，slow落在1上
       while(fast!=null&&fast.next!=null){
           slow=slow.next;
           fast=fast.next.next;
       }
       //记录slow的落点的下一个，它是右分组的起点 
       ListNode temp  = slow.next;
       //断开两段链表 
       slow.next=null;
       slow = temp;
       ListNode left = sortInList(head);
       ListNode right = sortInList(slow); 
       //合并两段有序链表 
       ListNode nodeHeda = new ListNode(-1);
       ListNode node = nodeHeda;
       while(left!=null&&right!=null){
           if(left.val>=right.val){
               node.next=right;
               right=right.next;
           }
           else{
               node.next=left;
               left=left.next;
           }
           node=node.next;
       }
       node.next=(left==null? right:left);
       return nodeHeda.next;
    }