-
3.9
- 因为是递归，所以判断好结束条件：是不是大于等于两个节点
- fast 先走一步，防止两个节点时死循环
-
2.11
- 递归剪断交给 merge
| 特性 | 回文链表 (Palindrome) | 归并排序 (Sort List) |
|---|---|---|
| 操作目的 | 找起点：只为了找到后半段从哪开始，好去反转它。 | 切分：必须把链表切成两段长度严格小于原长度的子链表。 |
| 对两个节点的要求 | 只要 slow 能跑到第 2 个节点就行，不管它是不是中点，它就是后半段。 | 必须切成 [1] 和 [2]。如果切分失败导致一边是 [1, 2]，一边是 []，递归就死循环。 |
| 推荐初始化 | fast = head (简单直观，偶数时 slow 在 n/2 + 1) | fast = head.next (偏左，保证偶数时 slow 在 n/2，方便切断，slow.next=null) |
2. 微观视角：压栈与出栈（拆解 [4, 2, 1, 3]）
为了彻底搞懂，我们来人肉跑一遍 [4, 2, 1, 3] 的排序过程。
第一阶段：“递” —— 层层外包（压栈）
程序会一直执行 sortList，直到把链表切得只剩 1 个节点（因为 1 个节点本身就是有序的，这是递归的终点）。
第一层（大老板）：拿到 [4, 2, 1, 3]。
切分：左 [4, 2]，右 [1, 3]。
呼叫 A：sortList([4, 2])。（程序暂停，等待 A 的结果）
第二层（外包 A）：拿到 [4, 2]。
切分：左 [4]，右 [2]。
呼叫 A1：sortList([4])。（程序暂停，等待 A1 的结果）
第三层（外包 A1）：拿到 [4]。
触发终止条件：if (head.next == null) return head;
A1 回复：“我干完了，给你 [4]”。
第二阶段：“归” —— 收工合并（出栈）
现在开始往回走了，大家开始兑现承诺，进行 merge。
回到第二层（外包 A）：
A1 回来了，左边是 [4]。
A 继续呼叫 A2：sortList([2])。
A2 也是单个节点，直接返回 [2]。
A 开始干活（Merge）：A 手里有左 [4] 和右 [2]。合并它们变成 [2, 4]。
A 回复大老板：“我干完了，给你 [2, 4]”。
回到第一层（大老板）：
A 回来了，左边是 [2, 4]。
老板继续呼叫 B：sortList([1, 3])。
（... B 的过程和 A 一模一样，会切成 [1] 和 [3]，然后合并成 [1, 3] ...）
B 回复大老板：“我干完了，给你 [1, 3]”。
大老板的最后一步：
左手拿着 [2, 4]（有序）。
右手拿着 [1, 3]（有序）。
老板干活（Merge）：合并这两个链表 -> [1, 2, 3, 4]。
返回最终结果。
3. 代码里的“暂停”机制
看这两行代码：
Java
ListNode left = sortList(head); // <--- 代码停在这里！
ListNode right = sortList(mid); // <--- 等上一行彻底做完了，才会执行这一行
return merge(left, right); // <--- 等上面两行都做完了，才会执行这一行
很多同学看不懂递归，是因为以为这三行是“瞬间”执行完的。 其实，当 sortList(head) 被调用时，程序会钻进那个函数里去，原来的函数就**挂起（Suspended）**了，保留现场，等待那个钻进去的函数 return 回来，它才继续往下走。
这就是**栈（Stack）**的概念。
-
1.20
- 快慢指针找中点（快的先走一步）+递归后 merge（类似与链表相加那个操作）（需要哨兵节点加尾指针）
-
11.11
- 双指针找中点(靠左)时,判断next||next.next,而不是之前
- 在确认位置时,需要断开中链,slow.next=null
- 先遍历断开,再放入merge
- merge需要哨兵节点,判大小,连接
class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
// ListNode ptr = head;
// int count = 0;
// while(ptr!=null){
// ptr = ptr.next;
// count++;
// }
// ListNode slow = head;
// for(int i=0;i<count/2-1;i++){
// slow = slow.next;
// }
这里应该在 count/2-1 这里停止，即中点的前一个
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left,right);
}
public ListNode merge(ListNode l1,ListNode l2){
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while(l1 != null&&l2 != null){
if(l1.val<=l2.val){
tail.next = l1;
l1 = l1.next;
}else{
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1==null)? l2:l1;
return dummy.next;
}
}找到链表中点（快慢指针法）。 将链表从中间断开，分成左右两个子链表。 递归地对左右子链表排序。 合并两个已排序的子链表（merge 两个有序链表）。