缺少递归终止条件导致无限调用 mergesort，最终耗尽调用栈；必须在递归前添加基础情况判断（如空链表或单节点），才能确保归并排序正确执行。
在您提供的链表归并排序实现中，mergeSort() 方法存在一个致命缺陷：没有递归出口（base case）。这意味着即使链表只有一个节点或为空，方法仍会继续拆分并递归调用自身，从而陷入无限递归，最终触发 StackOverflowError —— 这正是报错发生在 mergeSort(head) 左半部分调用处的根本原因。
✅ 正确做法：添加递归终止条件
应在执行快慢指针分割前，首先检查链表是否满足“已有序”的基本情况：
- head == null：空链表，直接返回；
- head.next == null：仅含一个节点，天然有序，直接返回。
修正后的 mergeSort 方法如下：
public static LinkedListNode<Integer> mergeSort(LinkedListNode<Integer> head) {
// ✅ Base case: empty list or single node → already sorted
if (head == null || head.next == null) {
return head;
}
// Split the list into two halves using slow-fast pointers
LinkedListNode<Integer> slow = head, fast = head, temp = null;
while (fast != null && fast.next != null) {
temp = slow;
slow = slow.next;
fast = fast.next.next;
}
// Break the link to separate left and right halves
temp.next = null;
// Recursively sort both halves
LinkedListNode<Integer> left = mergeSort(head); // now safe: left has size ⌊n/2⌋
LinkedListNode<Integer> right = mergeSort(slow); // right has size ⌈n/2⌉
// Merge the sorted halves
return merge(left, right);
}? 同时修复 merge() 中的逻辑错误
原 merge() 方法末尾存在两处严重 Bug：
- head1=head1.next; 在 if(head1!=null) 块中多余且无意义；
- current_node=head2; 错误地覆盖了指针，应为 current_node.next = head2;
✅ 修正后的 merge() 如下：
public static LinkedListNode<Integer> merge(LinkedListNode<Integer> head1, LinkedListNode<Integer> head2) {
LinkedListNode<Integer> dummy = new LinkedListNode<>(0);
LinkedListNode<Integer> current = dummy;
while (head1 != null && head2 != null) {
if (head1.data <= head2.data) {
current.next = head1;
head1 = head1.next;
} else {
current.next = head2;
head2 = head2.next;
}
current = current.next;
}
// Attach remaining non-null list (only one can be non-null)
current.next = (head1 != null) ? head1 : head2;
return dummy.next;
}⚠️ 注意事项总结
- 永远不要省略递归基线条件：对链表操作尤其敏感，n=0 和 n=1 必须显式处理；
- 分割后务必断开链接（temp.next = null），否则右半部分仍指向左半部分，造成环或重复遍历；
- merge() 的尾部连接必须使用 current.next = ...，而非直接赋值 current = ...，否则会丢失链表结构；
- 若 LinkedListNode 未提供泛型构造函数（如 new LinkedListNode(0)），请确保其支持传参初始化，否则需调整默认值逻辑。
通过以上修正，算法时间复杂度保持为 $O(n \log n)$，空间复杂度为 $O(\log n)$（递归栈深度），可稳定完成链表归并排序。
