2.1递增链表的合并
题目描述：
设计一个算法将两个递增链表合并成一个递增链表，仍使用原来的存储空间，不
申请新的存储空间，且新表中不能有重复元素。
假设要合并的两个链表的元素都是一次递增的。
算法思想：
设立三个指针pa,pb,pc,其中pa，pb执行LA,和LB中待比较的结点，而pc执行LC表当前最后一个结点。pa,pc的初始值为：pa,pb指向LA和LB的第一个结点，pc执行LC的头结点。
通过比较pa，pb所指向的结点的值：
当pa->data<pb->data时，选择pa指向的结点插入到LC的后面；当pa->data>pb->data时，选择pb指向的结点插入到LC的后面；当pa->data==pb->data时，将pb指针后移，pa指针不变。
void Combine(LinkList &L1,LinkList &L2,LinkList &L3){
struct LNode *pa,*pb;
pa=L1->next;
pb=L2->next;
L3=L1;
struct LNode *pc;
pc=L3;
while(pa&&pb){
if(pa->data<pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}else if(pa->data==pb->data){
pb=pb->next;
}else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
delete L2;
}
另外一种写法：
这种算法的思路和前面的是相同的，但是当两个值相同时，取其中一个的同时删除了另外一个元素。
<pre name="code" class="cpp">void Combine(LinkList &L1,LinkList &L3){
struct LNode *p1,*p2,*p3;
p1=L1->next;
p2=L2->next;
L3=L1;
p3=L3;
while(p1&&p2){
if(p1->data<p2->data){//取较小的元素
p3->next=p1;
p3=p1;
p1=p1->next;
}else if(p1->data>p2->data){//取较小的元素
p3->next=p2;
p3=p2;
p2=p2->next;
}else{
p3=p1->next;//相同时取p1所指的元素
p3=p1;
p1=p1->next;
struct LNode *q;//取p1后 删除p2
q=p2->next;
delete p2;
p2=q;
}
}
p3->next=p1?p1:p2;
delete L2;
}
算法分析：
该算法在归并两个链表时，不需要令建新的表空间，只需要将原来两个表的连接关系解除即可，因此该算法的空间复杂度是O(1)。由于LA和LB表中的元素是递增的，所以，对LB中的每个元素，不需要在LA中从表头至表尾进行全程搜索，如果LA和LB的长度分别是m和n，则该算法的时间复杂度是O(m+n)。
具体实现：
/* 设计一个算法将两个递增链表合并成一个递增链表，仍使用原来的存储空间，不 申请新的存储空间，且新表中不能有重复元素。 */ #include<stdio.h> #define MAX 100 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; int InitList(LinkList &L){ L=new LNode; L->next=NULL; return 1; } int ListLength(LinkList &L){ int length=0; struct LNode *p; p=L->next; while(p){ p=p->next; ++length; } return length; } void TraveList(LinkList L){ struct LNode *p; p=L->next; while(p){ printf("%d ",p->data); p=p->next; } printf("\n"); } void CreateList(LinkList &L,int n){ L=new LNode; L->next=NULL; struct LNode *r; r=L; printf("请按递增顺序输入链表元素:\n"); for(int i=0;i<n;i++){ printf("请输入第%d个元素的值:",i+1); struct LNode *s; s=new LNode; scanf("%d",&s->data); s->next=NULL; r->next=s; r=s; } } void Combine(LinkList &L1,*pb; pa=L1->next; pb=L2->next; L3=L1; struct LNode *pc; pc=L3; while(pa&&pb){ if(pa->data<pb->data){ pc->next=pa; pc=pa; pa=pa->next; }else if(pa->data==pb->data){ pb=pb->next; }else{ pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; delete L2; } int main(){ LinkList L1,L2,L3; if(InitList(L1)){ printf("表L1初始化成功!\n"); }else{ printf("表L1初始化失败!\n"); } if(InitList(L2)){ printf("表L2初始化成功!\n"); }else{ printf("表L2初始化失败!\n"); } if(InitList(L3)){ printf("表L3初始化成功!\n"); }else{ printf("表L3初始化失败!\n"); } printf("表L1的长度是:%d\n",ListLength(L1)); printf("请输入L1的长度:"); int n1; scanf("%d",&n1); CreateList(L1,n1); TraveList(L1); printf("请输入L2的长度:"); int n2; scanf("%d",&n2); CreateList(L2,n2); TraveList(L2); Combine(L1,L3); TraveList(L3); //TraveList(L2); }
第二中写法的实现：
/** 设计一个算法，将；两个递增链表合并成一个递增的链表，不能开辟新的空间，利用原来的空间 新表中不能有重复的元素 */ #include<stdio.h> #define MAX 100 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; int InitList(LinkList &L){ L=new LNode; L->next=NULL; return 1; } void TraveList(LinkList L){ struct LNode *p; p=L->next; while(p){ printf("%d ",int n){ L=new LNode; L->next=NULL; struct LNode *r; r=L; for(int i=0;i<n;i++){ printf("请输入链表第%d个元素的值:",*p3; p1=L1->next; p2=L2->next; L3=L1; p3=L3; while(p1&&p2){ if(p1->data<p2->data){//取较小的元素 p3->next=p1; p3=p1; p1=p1->next; }else if(p1->data>p2->data){//取较小的元素 p3->next=p2; p3=p2; p2=p2->next; }else{ p3=p1->next;//相同时取p1所指的元素 p3=p1; p1=p1->next; struct LNode *q;//取p1后 删除p2 q=p2->next; delete p2; p2=q; } } p3->next=p1?p1:p2; delete L2; } int main(){ LinkList L1,L3; if(InitList(L1)){ printf("L1初始化成功!\n"); }else{ printf("L1初始化失败!\n"); } if(InitList(L2)){ printf("L2初始化成功!\n"); }else{ printf("L2初始化失败!\n"); } if(InitList(L3)){ printf("L3初始化成功!\n"); }else{ printf("L3初始化失败!\n"); } printf("请输入L1的长度:"); int n1; scanf("%d",L3); printf("合并后的链表:\n"); TraveList(L1); }
