LeetCode hot100-33-Y

148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 

这题能通过但是投机取巧了，一般应该不能这样做，直接把节点里的值拿出来，排序后再更新每个节点的值。

/**
 * 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 {
    public ListNode sortList(ListNode head) {
        List<Integer> num = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            num.add(p.val);
            p = p.next;
        }
        Collections.sort(num);
        p = head;
        int i = 0;
        while (p != null) {
            p.val = num.get(i);
            p=p.next;
            i++;
        }
        return head;
    }
}

官方解法太长了，去网上找了另外一个解法。就是归并排序的思想。实际上执行的时间和空间还不如投机取巧的解法，但是这种应该可以面试的时候用
像这种归并排序的递归，连续三个方法都在递归，不知道每次递归的参数是什么，放编译器执行以下真正的归并排序代码，去感受以下迭代是怎么走的。（代码附在最后）

解法来自
https://zhuanlan.zhihu.com/p/434174362

class Solution {
    public ListNode sortList(ListNode head) {
        //如果链表为空，或者只有一个节点，直接返回即可，不用排序
        if (head == null || head.next == null)
            return head;
        
        //快慢指针移动，以寻找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next !=null){
          fast = fast.next.next;
          slow = slow.next;
        }
        //找到中间节点，slow节点的next指针，指向mid
        ListNode mid = slow.next;
        //切断链表
        slow.next = null;
        
        //排序左子链表
        ListNode left = sortList(head);
        //排序左子链表
        ListNode right = sortList(mid);
        
        //合并链表
        return merge(left,right);
    }
    
    public ListNode merge(ListNode left, ListNode right) {
       ListNode head = new ListNode(0);
       ListNode temp = head;
       while (left != null && right != null) {
           if (left.val <= right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        if (left != null) {
            temp.next = left;
        } else if (right != null) {
            temp.next = right;
        }
        return head.next;
    }
}

归并排序

public class MergeSort {
 
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        sort(arr, 0, arr.length - 1);
    }
 
    private static void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
 
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
 
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
 
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
 
        while (j <= right) {
            temp[k++] = arr[j++];
        }
 
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
 
    // 测试归并排序
    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
        mergeSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}