c++ - 合并两个排序的链表

我想通过指针操作来合并两个排序的链接列表，但此刻仍然停留。无法找出错误。请帮帮我。我认为问题出在while循环中。我想提高其空间利用率，并且不想再列出其他列表。

#include<iostream>
#include<conio.h>
using namespace std;
struct s
{
   int info;
   s *next;
};

int main()
{
    int i;
    char choice = 'y';
    s *ptr1, *ptr2, *start1, *start2, *reversedHead, *temp;
    ptr1= new s;
    start1=ptr1;
    cout<<"SIZE OF A NODE IS "<<sizeof(s)<<" BYTES"<<endl<<endl;
    while(choice=='y')
    {
                  cout<<"Enter info for node: ";
                  cin>>i;
                  ptr1->info = i;
                  cout<<"Do you wish to enter more nodes.? 'y'/'n'"<<endl;
                  cin>>choice;

                  if(choice=='y')
                  {
                                 ptr1->next = new s;
                                 ptr1 = ptr1->next;
                  }
                  else
                  {
                      ptr1->next = NULL;
                  }
    }
    choice = 'y';
    ptr2= new s;
    start2=ptr2;
    cout<<"SIZE OF A NODE IS "<<sizeof(s)<<" BYTES"<<endl<<endl;
    while(choice=='y')
    {
                  cout<<"Enter info for node: ";
                  cin>>i;
                  ptr2->info = i;
                  cout<<"Do you wish to enter more nodes.? 'y'/'n'"<<endl;
                  cin>>choice;

                  if(choice=='y')
                  {
                                 ptr2->next = new s;
                                 ptr2 = ptr2->next;
                  }
                  else
                  {
                      ptr2->next = NULL;
                  }
    }

    ptr1=start1;
    ptr2=start2;
    while(ptr1->next!=NULL || ptr2->next!=NULL)
    {
                         if(ptr1->info < ptr2->info)
                         {
                                       if(ptr1->next->info < ptr2->info)
                                                           ptr1=ptr1->next;
                                       else
                                       {
                                           ptr2=temp;
                                           ptr2=ptr2->next;
                                           temp->next=ptr1->next;
                                           ptr1->next=temp;
                                       }
                         }
                         else
                         {
                             if(ptr2->next->info < ptr1->info)
                                                 ptr2=ptr2->next;
                             else
                             {
                                 ptr1=temp;
                                 ptr1=ptr1->next;
                                 temp->next=ptr2->next;
                                 ptr2->next=temp;
                             }
                         }
    }
    if(ptr1->next==NULL)
                    ptr1->next=ptr2;
    else
        ptr2->next=ptr1;
    cout<<"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX";
    if(start1->info>start2->info)
    {
                             ptr2=start2;
                             while(ptr2!=NULL){
                                              cout<<ptr2->info<<"\t";
                                              ptr2=ptr2->next;}
    }
    else
    {
                             ptr1=start1;
                             while(ptr1!=NULL){
                                              cout<<ptr1->info<<"\t";
                                              ptr1=ptr1->next;}
    }



    getch();
}

最佳答案

您的while循环条件不太正确。

while(ptr1->next!=NULL || ptr2->next!=NULL)

很好，但仅当两个列表的长度相同时才可以！如果列表的长度不同，则ptr1->next或ptr2->next将是NULL，并且会出现分段错误。更改为&&是不正确的事情，因为您将失去列表之一的结尾！

用这个：

while((ptr1 != NULL && ptr2 != NULL) && (ptr1->next!=NULL || ptr2->next!=NULL))

现在，在循环中，您将进行如下测试：

if(ptr1->next->info < ptr2->info)

替换为

if(ptr1 != NULL && ptr1->next->info < ptr2->info)

这样长度不等的列表不会尽早终止，也不会在其中进行段错误。

接下来，在插入操作中，您将执行以下操作

ptr1=temp;
ptr1=ptr1->next

和

ptr2=temp;
ptr2=ptr2->next;

这很不好，因为temp是未定义的，因为您永远不会向其中写入任何有效数据！这里的错误是您的分配方式错误。您应该分别完成temp=ptr1和temp=ptr2。

最后，用于修复等长输入列表的清理操作需要考虑以下事实：不等长的输入列表可能导致ptr1或ptr2为NULL：

if(ptr1 != NULL && ptr1->next==NULL)
    ptr1->next=ptr2;
else if (ptr2 != NULL)
    ptr2->next=ptr1;

一切似乎都很好。我已经在1 3 5，2 4 6和1 3，2和1 4，2 3和1 3，2 3上测试了生成的代码，并且所有的工作都符合我的期望。