链表归并排序触发无限递归及栈溢出问题求助

我正在为链表实现归并排序，对应LeetCode的排序链表题目。以下是我的代码：

void mergesort(ListNode* head,ListNode* low, ListNode* high){
    ListNode* slow = low;
    ListNode* fast = low;
    if (low==high) return;
    while (fast->next && fast->next->next){
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* mid = slow;
    ListNode* mid1 = mid->next;
    mid->next == NULL;
    mergesort(head,low,mid);
    mergesort(head,mid1,high);
    merge(head,low,mid,high);
}
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* traverse = head;
        while(traverse->next){
            traverse = traverse->next;
        }
        ListNode* high = traverse;
        cout<<high->val;
        ListNode* low = head;
        mergesort(head,low,high);
        return head;
    }
};

即使注释掉merge函数，问题仍然存在，以下是merge函数代码供参考：

void merge(ListNode* head, ListNode* low, ListNode* mid, ListNode* high){
    ListNode* left = low;
    ListNode* right = mid->next;
    ListNode* dummy = new ListNode(-1);
    ListNode* tp = dummy;
    while(right && left!=mid->next){
        if (left->val<right->val){
            dummy->next = left;
            dummy = left;
            left = left->next;
        }
        if (left->val>right->val){
            dummy->next = right;
            dummy = right;
            right = right->next;
        }
    }
    if (right == NULL){
        while (left!=mid->next){
            dummy->next = left;
            left = left->next;
        }
    }
    if (left == mid->next){
        while(right){
            dummy->next = right;
            right = right->next;
        }
    }
    ListNode* start1= tp->next;
    head = start1;
}

我尝试采用类似线性数组的归并排序思路实现，自己推演时认为base case（low==high）会被触发，但实际运行时并未触发，且抛出如下错误：

AddressSanitizer:DEADLYSIGNAL
22ERROR: AddressSanitizer: 栈溢出，地址为0x7ffc9d343ff8 (pc 0x562648afe76b bp 0x7ffc9d344020 sp 0x7ffc9d344000 T0)
22ABORTING

问题分析与修复方案 #

1. 递归无限循环导致栈溢出的核心原因

mid->next == NULL; 这里误用了双等号（比较运算符），而非赋值运算符=，导致链表没有被切断。递归时子链表仍然包含整个原链表的节点，永远无法触发low==high的base case，最终造成无限递归、栈溢出。

修复：将该行改为 mid->next = NULL;。

2. 空指针风险处理

当输入链表为空（head == NULL）时，sortList函数中traverse->next会直接崩溃，需要先判断边界情况：

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head; // 空链表或单个节点直接返回
    // ... 原有代码
}

3. merge函数的问题修复

• 条件判断互斥：两个if (left->val>right->val)应该改为else if，否则可能同时执行两个分支，导致链表节点被错误覆盖。
• 终止节点置空：合并完成后，需要把最后一个节点的next设为NULL，避免出现链表环。
• 有效修改原链表：head = start1;是传值参数，修改不会影响外部的head指针。可以让merge返回合并后的头节点，或者在mergesort中正确连接合并后的链表到原结构中。

修复后的merge示例：

ListNode* merge(ListNode* left, ListNode* right) {
    ListNode* dummy = new ListNode(-1);
    ListNode* curr = dummy;
    while (left && right) {
        if (left->val <= right->val) {
            curr->next = left;
            left = left->next;
        } else {
            curr->next = right;
            right = right->next;
        }
        curr = curr->next;
    }
    curr->next = left ? left : right;
    return dummy->next;
}

4. 调整mergesort逻辑

修改后的mergesort可以改为返回子链表的头节点，更符合链表归并排序的常规实现：

ListNode* mergesort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow->next;
    slow->next = NULL;
    ListNode* left = mergesort(head);
    ListNode* right = mergesort(mid);
    return merge(left, right);
}

此时sortList函数可以简化为：

ListNode* sortList(ListNode* head) {
    return mergesort(head);
}

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