合并两个排序的链接列表

本文介绍了合并两个排序的链接列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想通过指针操作合并两个排序的链接列表，但停留在这一点。不能找出错误。请帮帮我。我认为问题是在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<<NODE IS的大小<<< sizeof（s）<<BYTES<< endl<< endl; while（choice =='y'） { cout<<输入节点信息：; cin>> i; ptr1-> info = i; cout<<你想输入更多的节点吗？'y'/'n'<< endl; cin>>选择; if（choice =='y'） { ptr1-> next = new s; ptr1 = ptr1-> next; } else { ptr1-> next = NULL; } } choice ='y'; ptr2 = new s; start2 = ptr2; cout<<NODE IS的大小<<< sizeof（s）<<BYTES<< endl< while（choice =='y'） { cout<<输入节点信息：; cin>> i; ptr2-> info = i; cout<<你想输入更多的节点吗？'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-& 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<<XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX; 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（ptr1-> next！= NULL || ptr2-> next！= NULL）

很好，但仅当两个列表长度相同时才会出现！当列表长度不同时， ptr1-> next 或 ptr2-> next 将为 NULL ，你会得到一个分段错误。更改为&& 不是正确的操作，因为您将丢失其中一个列表的结尾。

使用此方法：<（ptr1！= NULL& ptr2！= NULL）&& ptr2使用这个：

;&（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 >

I wanted to merge two sorted link lists by pointer manipulation, but stuck at this point. cant find out the mistake. Help me please. I think the problem is in while loop. I want to make it space efficient and do not want to make another list.

#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(); }

解决方案

Your while loop condition is not quite right.

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

is fine, but only when both lists are the same length!. When the lists are of different lengths, either ptr1->next or ptr2->next will be NULL, and you'll get a segmentation fault. Changing to to && is not the correct thing to do, because you'll lose the end of one of your lists!

Use this:

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

Now, inside your loop you have tests like this:

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

replace this with

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

so that unequal length lists don't terminate early and don't segfault inside.

Next, inside your insert operations, you do things like

ptr1=temp; ptr1=ptr1->next

and

ptr2=temp; ptr2=ptr2->next;

This is bad, because temp is undefined as you never write any valid data to it! The bug here is that your assignments are the wrong way round. You should have done temp=ptr1 and temp=ptr2 respectively.

Finally, your cleanup operation to fix up equal length input lists needs to account for the fact that unequal length input lists can result in either ptr1 or ptr2 being NULL:

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

And all seems to be well. I've tested the resulting code on 1 3 5,2 4 6 and 1 3,2 and 1 4,2 3 and 1 3,2 3 and all work as I'd expect them to.