148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入：head = [4,2,1,3]
输出：[1,2,3,4]
实例2
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
实例三
输入：head = []
输出：[]
大概思路：
自顶向下归并排序
对链表自顶向下归并排序的过程如下。
找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11，即当链表为空或者链表只包含 11 个节点时，不需要对链表进行拆分和排序。
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
就是说给定一个链表之后我们要把链表递归划分，直到不能划分为止。
https://leetcode-cn.com/problems/sort-list/solution/jin-dao-gui-bing-pai-xu-kan-tu-jiu-dong-wz6y1/)
如何确定链表重点呢，我们需要使用快慢指针的方法，fast一次走两步，slow一次走一步。当fast走到结尾，slow就处于中间位置。
为什么代码的{}被转译了呢
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) {
return head;
}
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
ListNode list1 = sortList(head, mid);
ListNode list2 = sortList(mid, tail);
ListNode sorted = merge(list1, list2);
return sorted;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead=new ListNode(0);
ListNode temp=dummyHead,temp1=head1,temp2=head2;
while(temp1!=null && temp2!=null){
if(temp1.val<temp2.val){
temp.next=temp1;
temp1=temp1.next;
}else{
temp.next=temp2;
temp2=temp2.next;
}
temp=temp.next;
}
if(temp1!=null){
temp.next=temp1;
}
if(temp2!=null){
temp.next=temp2;
}
return dummyHead.next;
}
}
