完整程序:
/*将两个有序递增链表合并成一个有序递增链表,要求结果仍使用原来两个链表的存储空间,不另外占有空间。*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20;
typedef struct LNode{
int data;
struct LNode *next;
} LNode,*LinkList;
LinkList mergelinklist(LinkList La,LinkList Lb){
//已知链表La,Lb的元素按递增排序。
//将两链表合并,仍然使用La的表头,将两个表比较,依次将存储空间连到La上。
//要合并后的链表仍然是递增的,需要尾插法。
LinkList pa,pb; //定义两个指针又来存储La,lb从首元结点开始向后的链表
pa=La->next; //La链表已经赋值给了pa,这样就可以使用La的头结点,作为新链表的头结点。
pb=Lb->next;
free(Lb); //Lb从首元结点开始已经赋值给了pb,所以把Lb,的头结点释放。
LinkList last=La; //last存储尾结点的地址。
while(pa&&pb){
if(pa->data<pb->data)
{
LinkList p=pa->next; //先把pa的下一个结点地址存储下来。
pa->next=NULL; //用尾插法将pa当前结点插入La。
last->next=pa;
last=last->next;
pa=p; //pa后移一位。
}
else if(pa->data==pb->data){ //值相等的情况
LinkList p=pa->next; //将pa当前结点插入La.
pa->next=NULL;
last->next=pa;
last=last->next;
pa=p; //pa后移一位
LinkList q=pb;
pb=pb->next; //释放当前结点,并且后移一位
free(q);
}
else{
LinkList p=pb->next; //指向pb后一个结点
pb->next=NULL; //把pb结点的next置空
last->next=pb; //此时pb中的元素比pa中的小,应把pb链接到pa的前面
last=last->next; //把last指针后移,保持last一直指向最后一个结点
pb=p; //pb后移一位,对下一个结点元素进行与pa的比较
}
}
last->next=pa?pa:pb; //pa,pb哪一个链表还没完,就将它连接到La后面。
return La;
}
int main(){
LinkList La,Lb;
int n,m,i;
La=(LinkList)malloc(sizeof(LNode));
La->next=NULL;
Lb=(LinkList)malloc(sizeof(LNode));
Lb->next=NULL;
LinkList last=La;
printf("请输入第一个有序递增表的长度:");
scanf("%d",&n);
printf("\n");
printf("请输入第一个有序递增表的元素:");
for(i=0;i<n;i++)
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=NULL;
last->next=p;
last=last->next;
}
last=Lb;
printf("\n");
printf("请输入第二个有序递增表的长度:");
scanf("%d",&m);
printf("\n");
printf("请输入第二个有序递增表的元素:");
for(i=0;i<m;i++)
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=NULL;
last->next=p;
last=last->next;
}
printf("\n");
La=mergelinklist(La,Lb);
LinkList p=La;
p=p->next;
printf("合并后的有序表为:");
while(p){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
return 0;
}
解析图: