链表归并排序代码出现运行时错误，求排查修复方案

尝试实现链表的归并排序，使用了三个核心函数：

• mid：查找链表中点
• merge：合并两个有序链表
• mergeSort：递归执行归并排序的主函数

Node类结构如下：

class Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

原代码存在运行时错误，核心问题出在mergeSort函数的递归终止条件缺失。

错误原因分析 #

当前mergeSort仅处理了head == NULL的情况，但当链表只有一个节点（head->next == NULL）时，代码仍会执行拆分操作：

• 调用mid函数会返回该节点本身，half2被赋值为NULL
• 随后递归调用mergeSort(half1)，再次进入相同逻辑，导致无限递归，最终触发栈溢出的运行时错误

修复方案 #

给mergeSort添加单个节点的终止条件：当链表只有一个节点时，直接返回该节点（单个节点天然有序，无需继续拆分）。

修改后的mergeSort函数代码：

Node *mergeSort(Node *head)
{
    // 终止条件：空链表 或 单个节点的链表
    if(head==NULL || head->next == NULL)
    {
        return head;
    }
    Node *midpoint = mid(head);
    
    Node *half1 = head;
    Node *half2 = midpoint->next;
    midpoint->next = NULL;
    
    half1 = mergeSort(half1);
    half2 = mergeSort(half2);
    
    Node *mergeHead = merge(half1,half2);
    
    return mergeHead;
}

其他函数验证 #

• mid函数：快慢指针逻辑正确，能正确找到链表中点（偶数节点时返回左中点），无需修改。
• merge函数：合并两个有序链表的逻辑完整，边界条件（其中一个链表为空）处理正确，无需修改。

修复后完整代码 #

class Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

Node *merge(Node *head1, Node *head2)
{
    Node *nh = NULL;
    Node *nt = NULL;
    
    if(head1==NULL)
    {
        return head2;
    }

    if(head2==NULL)
    {
        return head1;
    }

    if(head1->data<=head2->data)
    {
        nh = head1;
        nt = head1;
        head1 = head1->next;
    }
    else
    {
        nh = head2;
        nt = head2;
        head2 = head2->next;
    }
    
    while(head1!=NULL && head2!=NULL)
    {
        if(head1->data<=head2->data)
        {
            nt->next = head1;
            nt = head1;
            head1=head1->next;
        }
        else
        {
            nt->next = head2;
            nt = head2;
            head2 = head2->next;
        }
    }
    
    if(head1!=NULL)
    {
        nt->next =head1;
    }
    if(head2!=NULL)
    {
        nt->next =  head2;
    }
    return nh;
}


Node *mid(Node *head)
{
    if(head==NULL)
    {
        return head;
    }
    Node *fast = head;
    Node *slow = head;
    
    while(fast->next!=NULL && fast->next->next!=NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}


Node *mergeSort(Node *head)
{
    if(head==NULL || head->next == NULL)
    {
        return head;
    }
    Node *midpoint = mid(head);
    
    Node *half1 = head;
    Node *half2 = midpoint->next;
    midpoint->next = NULL;
    
    half1 = mergeSort(half1);
    half2 = mergeSort(half2);
    
    Node *mergeHead = merge(half1,half2);
    
    return mergeHead;
}

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