【问题描述】两个有序单链表LA和LB的合并,请合并到LA表中再输出,LB表的空间全部释放。
【样例输入】
1 3 5 7 9 0
1 2 3 4 15 20 0
【样例输出】
1 2 3 4 5 7 9 15 20
【注意】0代表输入结束
#include <iostream>
#include<cstdlib>
using namespace std;
struct Node
{
int data;
Node *next;
};
typedef Node* LinkList;
//尾插法建立链表
LinkList CreateFormTail()
{
LinkList L;
Node *s,*r;
int x,flag=1;
L=new Node;
L->next = NULL;
r=L;
while(flag){
cin>>x;
if(x){
s=new Node;
s->data = x;
r->next = s;
r=s; //让s始终指向新创建的节点,而r始终指向上一个节点,来将整个链表相连
}
else{
flag = 0;
r->next = NULL;
}
}
return L;
}
//遍历输出
void Traver(LinkList p)
{
Node *s;
int a=0;
s=p->next;
while(s)
{
if(a==0){
cout<<s->data;
a++;
s=s->next;
}
else{
cout<<" "<<s->data;
s=s->next;
}
}
}
void DelLinkList(LinkList L)
{
Node *s=L,*r;
r=s->next;
while(r){
delete s;
s=r;
r=s->next;
}
delete s;
}
//编写合并函数
void MergeList(LinkList &LA,LinkList &LB)
{
LinkList pa,pb,pc;
pa=LA->next;
pb=LB->next;
pc=LA;
while(pa&&pb){
if(pa->data<pb->data){
pc->next = pa;
pc=pa;
pa=pa->next;
}
else if(pa->data>pb->data){
pc->next=pb;
pc = pb;
pb = pb->next;
}
else{
//这里需要去重
pc->next=pa;
pc=pa;
pa=pa->next;
pb = pb->next;
}
//从循环跳出来,即有其中一个链表已经达到末尾,此时接下另外一个列表的所有部分(由于这里链表的递增特性//
pc->next=pa?pa:pb;
DelLinkList(LB);
}
}
int main()
{
LinkList LA;
LinkList LB;
LA=CreateFormTail();
LB = CreateFormTail();
MergeList(LA,LB);
Traver(LA);
DelLinkList(LA);
delete(LA);
delete(LB);
return 0;
}