排序链表，
题目
力扣链接
水平有限，归并排序非递归的方法没弄出来，┭┮﹏┭┮
代码
package com.harrison.class200;
/*
* @author：Harrison
* @Times：2022年9月1日 下午12:51:18
* @motto：众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
*/
public class Code148_SortList {
// 归并排序递归版本，时间复杂度O(N*logN)，空间复杂度O(logN)
// 因为递归需要用到系统栈
public static ListNode sortList1(ListNode head) {
// 如果链表为空或只有一个结点，不用排序，直接返回
if (head == null || head.next == null) {
return head;
}
// 利用快慢指针找到链表的中点
ListNode slow = head;
ListNode fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 结束上面的while循环后，slow来到了链表的中点（奇数个）
// 如果链表为偶数个，slow来到链表的上中点
ListNode start = slow.next;// 链表截断后，start为第二段链表的头结点
slow.next = null;
ListNode left = sortList1(head);
ListNode right = sortList1(start);
// 用来找到合并之后新的头结点
ListNode h = new ListNode(0);
// 因为h会不断移动，所以新建一个引用pre记住h
ListNode pre = h;
// 合并两个有序链表（力扣第21题）
while (left != null && right != null) {
if (left.val <= right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return pre.next;
}
}