使用链表实现归并排序时为何出现栈溢出错误？

我帮你找到了栈溢出的核心原因——你的mid_element函数在拆分链表时，会导致无限递归，哪怕是只有5-6个元素的短链表也会触发这个问题。

问题分析 #

我们拿最简单的2节点链表（比如1->2）来举例：

1. 调用MergeSort时，因为head->next != NULL，会进入拆分逻辑。
2. 你的mid_element函数会返回第二个节点（2）。
3. 拆分后，第一部分是原链表（head到mid，也就是1->2），第二部分是mid->next也就是NULL。
4. 递归调用MergeSort(head)时，又会重复上述步骤：链表长度仍然大于1，再次找mid、拆分，永远无法触发递归终止条件（head->next == NULL）。

这种无限递归会不断消耗栈空间，最终导致栈溢出崩溃。

解决方案：修正mid_element函数 #

我们需要调整中间节点的查找逻辑，让它返回左半部分链表的最后一个节点，这样拆分后的左半部分不会包含整个链表，递归才能正常终止。

修正后的mid_element代码：

Node *mid_element(Node *head) {
    if(head == NULL || head->next == NULL)
        return head;
    Node *slow = head, *fast = head;
    // 循环条件改为检查fast的下一个和下下个节点，确保slow停在中间节点的前一个
    while(fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

额外优化：让Merge函数更健壮 #

虽然你提到Merge函数能正常工作，但当前实现没有处理其中一个链表为空的情况（虽然你的归并排序逻辑暂时不会传入空链表，但还是建议修正，避免潜在问题）：

Node *Merge(Node *h1, Node *h2) {
    // 先处理空链表的边界情况
    if(h1 == NULL) return h2;
    if(h2 == NULL) return h1;
    
    Node *h, *t;
    // 确定头节点
    if(h1->data < h2->data) {
        h = h1;
        h1 = h1->next;
    } else {
        h = h2;
        h2 = h2->next;
    }
    t = h;
    
    // 合并剩余节点
    while(h1 != NULL && h2 != NULL) {
        if(h1->data < h2->data) {
            t->next = h1;
            t = t->next;
            h1 = h1->next;
        } else {
            t->next = h2;
            t = t->next;
            h2 = h2->next;
        }
    }
    
    // 拼接剩余的非空链表
    if(h1 != NULL) t->next = h1;
    if(h2 != NULL) t->next = h2;
    
    return h;
}

验证修正效果 #

现在重新运行你的归并排序逻辑，不管是短链表还是长链表，都能正常拆分、递归排序并合并，不会再出现栈溢出问题。

内容的提问来源于stack exchange，提问作者Arman Atibudhi