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指针，指向midListNode 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 + " ");}}
}