设计一个算法，将两个递增链表La、Lb合并成一个递增链表Lc。

Answer 1

//设计一个算法，将两个递增链表La、Lb合并成一个递增链表Lc;La,Lb,Lc均为带头结点的链表
#include<stdio.h>
typedef int datatype;
struct PNode
{
datatype data; //定义链表中结点的数据域，DATATYPE为数据类型
struct PNode *next; //定义链表中结点的指针域
};
typedef struct PNode linklist;
linklist *ListCreateNull()
//建立带头结点的空单链表，返回头结点的地址
{ linklist *list;
list =(linklist *)malloc(sizeof(linklist));
//申请表头结点空间
if(list!=NULL) list->next=NULL;
else printf("Out of space! \n");
return list;
}
int ListInsert(linklist *L,datatype x)
//在链表L的尾部插入X,返回1表示成功，0表示失败
{
linklist *p,*q;
p=L;
while(p->next!=NULL)
p=p->next;
q=(linklist *)malloc(sizeof(struct PNode));
if(!q)return 0;
q->data=x;
p->next=q;
q->next=NULL;
return 1;
}
linklist *fun(linklist *La,linklist *Lb,linklist *Lc)
//将两个递增链表La、Lb合并成一个递增链表Lc
{
linklist *p;
p=Lc;
while(La->next!=NULL&&Lb->next!=NULL)
{
if(La->next->data>Lb->next->data)
{
ListInsert(p,Lb->next->data);
Lb=Lb->next;
}
else
{
ListInsert(p,La->next->data);
La=La->next;
}
}
if(La->next==NULL)
{
while(Lb->next!=NULL)
{
ListInsert(p,Lb->next->data);
Lb=Lb->next;
}
}
if(Lb->next==NULL)
{
while(La->next!=NULL)
{
ListInsert(p,La->next->data);
La=La->next;
}
}
return Lc;
}
main()
{
linklist *La,*Lb,*Lc;
int temp=1,i;
//初始化链表La
La=(linklist *)ListCreateNull();
printf("请输入数据以零结束：\n");
for(i=0;i<3;i++)
{
scanf("%d",&temp);
ListInsert(La,temp);
}
//初始化链表Lb
temp=1;
Lb=(linklist *)ListCreateNull();
printf("请输入数据以零结束：\n");
for(i=0;i<3;i++)
{
scanf("%d",&temp);
ListInsert(Lb,temp);
}
//初始化链表Lc
Lc=(linklist *)malloc(sizeof(struct PNode));
Lc->next=NULL;
Lc->data=NULL;
Lc=fun(La,Lb,Lc);
while(Lc->next!=NULL)
{
printf("%d ",Lc->next->data);
Lc=Lc->next;
}
printf("\n");
}

Answer 2

void merge()
{
int na=la.len;
int nb=lb.len;
int i=0,j=0;
int k=0;
while(i<na&&j<nb)
{
while(la[i]<=lb[j]&&i<na&&j<nb)
{
lc[k]=la[i];
i++;
k++;
}
while(lb[j]<=la[i]&&j<nb&&i<na)
{
lc[k]=lb[j];
j++;
k++;
}
}
while(i<na)
{
lc[k++]=la[i];
}
while(j<nb)
{
lc[k++]=lb[j];
}
}
这是一个伪代码，你自己再改改吧