排序链表，

题目

力扣链接

水平有限，归并排序非递归的方法没弄出来，┭┮﹏┭┮

代码

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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47