题目：
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
思路：
1.找链表中点【使用快慢指针 慢指针每次移动一步，快指针每次移动两步，当快指针移动到链表末尾时，慢指针则指向中点位置】
2.对两个链表分别进行递归排序
3.合并两个链表
代码：
/**
* 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) {
return sort(head, null);
}
// 使用归并排序 将链表一分为二 分别递归进行排序 对head-tail进行归并排序
public ListNode sort(ListNode head, ListNode tail){
// 链表判空 直接返回NULL
if(head == null){
return head;
}
if(head.next == tail){
// 如果只有一个节点 就返回这一个节点
head.next = null;
return head;
}
// 使用快慢指针找到链表中点 慢指针移动一步，快指针移动两步
ListNode slow = head;
ListNode fast = head;
while(fast != tail){
slow = slow.next;
fast = fast.next;
if(fast != tail){
fast = fast.next;
}
}
// 经过快慢指针 slow指向中点节点
ListNode mid = slow;
// 递归调用归并排序
ListNode list1 = sort(head,mid);
ListNode list2 = sort(mid, tail);
// 合并两个链表
ListNode sorted = merge(list1, list2);
return sorted;
}
// 合并两个已经排序的链表
public ListNode merge(ListNode head1, ListNode head2){
// 创建哑铃节点 作为合并链表的起始节点
ListNode dummyHead = new ListNode(0);
// temp用于遍历链表 temp1和temp2分别指向两个待合并链表的当前节点
ListNode temp = dummyHead;
ListNode temp1 = head1;
ListNode 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;
}
// 如果其中一个链表已经遍历完，则将剩余链表连接到temp中
if(temp1 != null){
temp.next = temp1;
}else{
temp.next = temp2;
}
return dummyHead.next;
}
}
