链表归并排序代码运行出现栈溢出错误求助

嘿，我来帮你排查下这段链表归并排序代码为啥会触发栈溢出～

先看你贴的代码，核心问题主要出在两个地方：

1. 递归终止条件缺失 #

你的sortList函数里只写了//base case注释，但没有实际实现终止逻辑！当链表为空或者只有一个节点时，本来应该直接返回，不需要再递归拆分。如果没加这个判断，递归会一直调用下去，不断消耗栈空间，最终导致溢出。

2. 中间节点查找逻辑有问题，导致无法正确拆分链表 #

当前的findMiddle函数，对于长度为2的链表，会返回第二个节点。这时候你拆分左右链表时，如果没把左链表的尾部和右链表断开，递归调用sortList(head)时，又会重复处理整个链表，陷入无限递归循环，这也是栈溢出的关键原因。

修正后的完整代码 #

ListNode *findMiddle(ListNode *head){
    if (!head || !head->next) return head;
    ListNode *slow = head;
    ListNode *fast = head->next;

    while (fast != nullptr && fast->next != nullptr){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode *merge(ListNode *left, ListNode *right ){
    ListNode *dummy = new ListNode(-1);
    ListNode *tmp = dummy;

    while (left != nullptr && right != nullptr){
        if (left->val < right->val){
            tmp->next = left;
            tmp = left;
            left = left->next;
        } else {
            tmp->next = right;
            tmp = right;
            right = right->next;
        }
    }

    // 处理剩余节点
    if (left) tmp->next = left;
    else tmp->next = right;
    
    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

ListNode* sortList(ListNode* head) {
    // 递归终止条件：空链表或只有一个节点，直接返回
    if (!head || !head->next) {
        return head;
    }

    // 找到左半部分的最后一个节点
    ListNode* mid = findMiddle(head);
    ListNode* right = mid->next;
    // 断开左右链表的连接，避免递归时重复处理
    mid->next = nullptr;

    // 递归排序左右子链表
    ListNode* leftSorted = sortList(head);
    ListNode* rightSorted = sortList(right);

    // 合并两个有序链表
    return merge(leftSorted, rightSorted);
}

关键修正点说明 #

• 给sortList补上了递归终止条件，当链表长度≤1时直接返回，停止递归。
• 调整了findMiddle的逻辑，让fast从head->next开始遍历，这样对于偶数长度的链表，slow会停在左半部分的最后一个节点，方便我们断开左右链表。
• 在拆分链表时，手动将mid->next设为nullptr，确保左右链表是完全独立的，避免递归时出现循环引用。

这样修改后，递归就能正常终止，不会再出现栈溢出的问题啦～

备注：内容来源于stack exchange，提问作者Amit Kumar