为什么我使用此函数进行合并排序（使用链表）时会出现堆栈溢出错误？

Question

我正在使用 mid_element() 函数来 return 中间节点的地址，并使用 Merge() 函数来合并两个已排序的链表。这两个功能都可以正常工作。但为了以防万一，我附上了代码。我经历了将链表分成两部分的合并排序算法，一个包含第一个节点到中间节点，另一个包含从 mid+1 到末尾的节点。当然，中间节点的下一个指针设置为空。然后我们在两半上递归调用合并排序，最后将两者合并。我做了同样的事情，但最终出现堆栈溢出错误。请帮忙。中间元素函数：

Node *mid_element(Node *head)
{
    if(head==NULL || head->next==NULL)
        return head;
    Node *slow=head,*fast=head->next;
    while(fast!=NULL)
    {
        if(fast->next==NULL)
        {
            slow=slow->next;
            break;
        }
        else
        {
            fast=fast->next->next;
            slow=slow->next;
        }
    }
    return slow;
}

合并函数：

Node *Merge(Node *h1,Node *h2)
{
    Node *h=h1->data<h2->data?h1:h2,*t=h;
    h1=h1->next;
    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;
}

合并排序函数：

Node *MergeSort(Node *head)
{
    if(head==NULL || head->next==NULL)
        return head;
    else
    {
        Node *mid=mid_element(head);
        Node *temp=mid->next;
        mid->next=NULL;
        Node *res1=MergeSort(head);
        Node *res2=MergeSort(temp);
        Node *res=Merge(res1,res2);
        return res;
    }
}

节点定义：

class Node
{
public:
    int data;
    Node *next;

    Node(int data)
    {
        this->data=data;
        next=NULL;
    }

};

我正在使用一个函数来获取输入。用户输入 space 分隔的数字列表，-1 表示列表结束。输入函数：

Node *takeInput()
{
    int data;
    Node *head=NULL,*temp=NULL,*curr=NULL;
    do{
        cin >> data;
        if(data!=-1)
        {
            temp=new Node(data);
            if(head==NULL)
            {
                head=curr=temp;
            }
            else
            {
                curr->next=temp;
                curr=curr->next;
            }

        }
    }while (data!=-1);
    return head;
}

关于列表的大小，我只检查了只有 5-6 个元素长的列表，结果崩溃了。

Answer 1

Merge() 中的这一行取消引用了一个潜在的空指针。

Node *h=h1->data<h2->data?h1:h2,*t=h;

它可能为空，因为 mid_element() 包含此行

if(head==NULL || head->next==NULL)
    return head;

... 可以 return 一个指针，其 next 元素为空，并且 MergeSort() 取该 return 值，得到 next 元素可能为空，并将其传递给 Merge().

底线：在取消引用指针之前需要进行更多空值检查。

为什么我使用此函数进行合并排序（使用链表）时会出现堆栈溢出错误？

Why do I get stack overflow error when I use this function for Merge Sort(using Linked Lists)?

c++

mergesort

linked-list