NC70：单链表的排序

解法1：归并排序

思路：先利用快慢指针找出链表的中点，然后分为两个链表，一直分，知道无法分为止，然后自底而上排序归并

public ListNode sortInList (ListNode head) {
        // write code here
        return mergerSort(head);
    }
    public ListNode mergerSort(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode  pre = null;
        while(fast != null && fast.next != null){
            pre=slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //       slow
        //       mid next
        // 1 3 4 [5] | 6  7 4 2
        pre.next = null;
        ListNode left = mergerSort(head);
        ListNode right = mergerSort(slow);

        return mergeList(left, right);
    }
     // dh ->
     // 1 2 3 4
     // 6 7 8 9
     public ListNode mergeList(ListNode left, ListNode right){
         ListNode dummyHead = new ListNode(0);
         ListNode cur = dummyHead;
        //ListNode cur = left.val < right.val ? left : right;

         while(left != null && right != null){
             if(left.val < right.val){
                 cur.next = left;
                 left = left.next;
             }
             else{
                 cur.next = right;
                 right = right.next;
             }
             cur = cur.next;
         }
         cur.next = left == null ? right : left;

         return dummyHead.next;
    }

解法2：选择排序

1.建立哨兵节点
2.每次从未排序的链表节点中找出最小的节点接到已排序链表的后面

public ListNode sortInList (ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode sorted = dummy;

    while (sorted.next != null) {
        ListNode pre = sorted;
        ListNode cur = sorted.next;
        ListNode preMin = null;
        ListNode min = null;
        while (cur != null) {
            if (min == null || cur.val < min.val) {
                preMin = pre;
                min = cur;
            }
            pre = pre.next;
            cur = cur.next;
        }

        preMin.next = min.next;
        min.next = sorted.next;
        sorted.next = min;
        sorted = min;
    }
    return dummy.next;
}

解法3：虚假的选择排序：交换链表中的值

public ListNode sortInList (ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode move = head;
    while (move.next != null) {
        ListNode temp = move.next;
        while (temp != null) {
            if (temp.val < move.val) {
                int val = temp.val;
                temp.val = move.val;
                move.val = val;
            }
            temp = temp.next;
        }
        move = move.next;
    }
    return head;
}