如何修复链表归并排序中的栈溢出错误（StackOverflowError）_技术教程

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

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

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

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

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

修正后的 mergeSort 方法如下：

public static LinkedListNode mergeSort(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 LinkedListNode merge(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;
}