实现链表(线性表)
时间： 1ms 内存：128M
描述：
（线性表）顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。
输入：
输入LA长度m：7
输入数据：3 7 11 15 57 68 99
输入LB长度n：7
输入数据：6 7 8 9 10 23 67
输出：
3 6 7 8 9 10 11 15 23 57 67 68 99
示例输入：
7
4 6 7 9 10 16 23
8
1 2 4 7 8 13 15 44示例输出：
1 2 4 6 7 8 9 10 13 15 16 23 44 提示：
参考答案（内存最优[0]）：
#include<iostream>
using namespace std;
struct line
{
int shu;
line *next;
};
void printfLine(line *head)
{
while(head)
{
cout<<head->shu<<" ";
head=head->next;
}
cout<<endl;
}
int main()
{
line *head1,*head2,*head3;
line *p1,*p2;
line *q1,*q2;
line *p;
int i,j;
int m,n;
cin>>m;
p1=p2=head1=new line;
for(i=0;i<m;i++)
{
cin>>p1->shu;
if(i!=m-1)
p1=p1->next=new line;
else
p1->next=NULL;
}
cin>>n;
q1=q2=head2=new line;
for(j=0;j<n;j++)
{
cin>>q1->shu;
if(j!=n-1)
q1=q1->next=new line;
else
q1->next=NULL;
}
p1=head1;
q1=head2;
p1=p1->next;
q1=q1->next;
if(head1->shu<=head2->shu)
{
head3=head1;
p2=p1;
p1=p1->next;
p=head3;
p->next=NULL;
}
else
{
head3=head2;
q2=q1;
q1=q1->next;
p=head3;
p->next=NULL;
}
while(1)
{
if(p2!=NULL&&q2!=NULL)
{
if(p2->shu<=q2->shu)
{
p=p->next=p2;
p2=p1;
if(p1!=NULL)
p1=p1->next;
}
else
{
p=p->next=q2;
q2=q1;
if(q1!=NULL)
q1=q1->next;
}
}
else if(p2==NULL&&q2!=NULL)
{
p->next=q2;
break;
}
else if(p2!=NULL&&q2==NULL)
{
p->next=p2;
break;
}
}
p=head3;
printfLine(p);
return 0;
}
参考答案（时间最优[0]）：
#include"stdio.h"
#include"stdlib.h"
typedef struct node
{
int data;
struct node *next;
}node;
node *create(node *head)
{
int i,len;
node *p1=0,*p2=0;
scanf("%d",&len);
for(i=0;i<len;i++)
{
p1=(node*)malloc(sizeof(node));
scanf("%d",&p1->data);
if(i==0)
head=p1;
else
p2->next=p1;
p2=p1;
}
p1->next=0;
return head;
}
node *Union(node *head1,node *head2)
{
node *head=0,*p;
if(head1->data<head2->data)
{
head=head1;
head1=head1->next;
}
else
{
head=head2;
head2=head->next;
}
p=head;
while(head1!=0&&head2!=0)
{
if(head1->data==head2->data)
{
head->next=head1;
head1=head1->next;
head2=head2->next;
head=head->next;
continue;
}
if(head1->data<head2->data)
{
head->next=head1;
head1=head1->next;
head=head->next;
}
else
{
head->next=head2;
head2=head2->next;
head=head->next;
}
}
if(head1==0)
head->next=head2;
else
head->next=head1;
return p;
}
int main(){
node *head1,*head2,*head;
head1=create(head1);
head2=create(head2);
head=Union(head1,head2);
printf("%d",head->data);
head=head->next;
while(head!=0)
{
printf(" %d",head->data);
head=head->next;
}
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。