缺少递归终止条件导致无限调用 mergesort，最终耗尽调用栈；必须在递归前添加基础情况判断（如空链表或单节点），才能确保归并排序正确执行。
在您提供的链表归并排序实现中，mergeSort() 方法存在一个致命缺陷：没有递归出口（base case）。这意味着即使链表只有一个节点或为空，方法仍会继续拆分并递归调用自身，从而陷入无限递归，最终触发 StackOverflowError —— 这正是报错发生在 mergeSort(head) 左半部分调用处的根本原因。
✅ 正确做法：添加递归终止条件
应在执行快慢指针分割前，首先检查链表是否满足“已有序”的基本情况：
- head == null：空链表，直接返回；
- head.next == null：仅含一个节点，天然有序，直接返回。
修正后的 mergeSort 方法如下：
public static LinkedListNodemergeSort(LinkedListNode 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 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 left = mergeSort(head); // now safe: left has size ⌊n/2⌋ LinkedListNode 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 LinkedListNodemerge(LinkedListNode head1, LinkedListNode head2) { LinkedListNode dummy = new LinkedListNode<>(0); LinkedListNode 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)$（递归栈深度），可稳定完成链表归并排序。
