缺少递归终止条件导致无限调用 mergesort，最终耗尽调用栈；必须在递归前添加基础情况判断（如空链表或单节点），才能确保归并排序正确执行。

在您提供的链表归并排序实现中，mergeSort() 方法存在一个致命缺陷：没有递归出口（base case）。这意味着即使链表只有一个节点或为空，方法仍会继续拆分并递归调用自身，从而陷入无限递归，最终触发 StackOverflowError —— 这正是报错发生在 mergeSort(head) 左半部分调用处的根本原因。

✅ 正确做法：添加递归终止条件

应在执行快慢指针分割前，首先检查链表是否满足“已有序”的基本情况：

• head == null：空链表，直接返回；
• head.next == null：仅含一个节点，天然有序，直接返回。

修正后的 mergeSort 方法如下：

NodeMaven – Premium Proxies for Account Management, Automation, and Scraping

提供端到端的高端代理设置和使用指导，包括代理类型选择、地区定向、访问配置、API密钥验证和监控。

下载

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：

1. head1=head1.next; 在 if(head1!=null) 块中多余且无意义；
2. 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)$（递归栈深度），可稳定完成链表归并排序。