调用归并排序处理链表前半部分时出现StackOverflowError如何解决？

导致StackOverflowError的核心原因 #

你的mergeSort方法缺少递归终止条件：当链表只剩单个节点（或为空）时，代码仍会执行拆分逻辑，导致无限递归调用mergeSort，最终触发栈溢出。

额外的merge方法逻辑错误 #

merge方法中处理剩余节点的代码存在bug：当head2有剩余节点时，错误地将current_node直接指向head2，而非把head2挂到current_node.next，这会导致合并后的链表断链。

修正后的完整代码 #

public class Solution {

    public static LinkedListNode<Integer> mergeSort(LinkedListNode<Integer> head) {
        // 递归终止条件：空链表或单个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }
        
        LinkedListNode slow = head, fast = head, temp = head;
        while (fast != null && fast.next != null) {
            temp = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        temp.next = null; // 拆分左右链表
        LinkedListNode left_side = mergeSort(head);
        LinkedListNode right_side = mergeSort(slow);

        return merge(left_side, right_side);
    }

    public static LinkedListNode<Integer> merge(LinkedListNode<Integer> head1, LinkedListNode<Integer> head2){
        LinkedListNode temp_node = new LinkedListNode(0);
        LinkedListNode current_node = temp_node;

        while (head1 != null && head2 != null) {
            if (head1.data <= head2.data) {
                current_node.next = head1;
                head1 = head1.next;
            } else {
                current_node.next = head2;
                head2 = head2.next;
            }
            current_node = current_node.next;
        }
        // 挂载剩余的head1节点
        if (head1 != null) {
            current_node.next = head1;
        }
        // 挂载剩余的head2节点（修正此处的赋值错误）
        if (head2 != null) {
            current_node.next = head2;
        }
        
        return temp_node.next;
    }
}

关键修正点说明 #

• 添加递归终止条件：在mergeSort开头判断head == null || head.next == null，直接返回原节点，避免无限递归。
• 修复merge方法的剩余节点处理：将current_node = head2改为current_node.next = head2，保证链表的连续性。

内容的提问来源于stack exchange，提问作者Shivam Kabra