任務(wù)描述
本關(guān)任務(wù)：給定兩個(gè)遞增的整數(shù)序列A和B，利用鏈表表示序列A和B，將A和B合并為一個(gè)遞增的有序序列C，序列C不允許有重復(fù)的數(shù)據(jù)。要求空間復(fù)雜度為O(1)。
編程要求
輸入
多組數(shù)據(jù)，每組數(shù)據(jù)有三行，第一行為序列A和B的長(zhǎng)度n和m，第二行為序列A的n個(gè)元素，第三行為序列B的m個(gè)元素（元素之間用空格分隔）。n=0且m=0時(shí)輸入結(jié)束。
輸出
對(duì)于每組數(shù)據(jù)輸出一行，為合并后的序列，每個(gè)數(shù)據(jù)之間用空格分隔。
測(cè)試說(shuō)明
平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-744494.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-744494.html
?代碼
#include <iostream>
#define OK 1
using namespace std;
typedef struct LNode
{
int data;
struct LNode* next;
}LNode, * LinkList;
void CreateList_R(LinkList& L, int n)
{//后插法創(chuàng)建單鏈表
L=new LNode;
L->next=NULL;
int i;
LinkList p=L;
for(i=1;i<=n;i++){
LinkList s;
s=new LNode;
scanf("%d",&s->data);
s->next=NULL;
p->next=s;
p=s;
}
}
int MergeList(LinkList& LA, LinkList& LB)
{//求基于鏈表的兩個(gè)遞增有序序列的合并 存入LA
LNode *r1 = LA -> next;
LNode *r2 = LB -> next;
LNode *r3 = LA;
while (r1 && r2)
{
if (r1 -> data < r2 -> data)
{
r3 -> next = r1;
r3 = r1;
r1 = r1 -> next;
}
else if (r1 -> data == r2 -> data)
{
r3 -> next = r1;
r3 = r1;
r1 = r1 -> next;
r2 = r2 -> next;
}
else
{
r3 -> next = r2;
r3 = r2;
r2 = r2 -> next;
}
}
if (r1) // 如果還有剩下，則只需要直接連接就好，不需要遍歷
r3 -> next = r1;
if (r2)
r3 -> next = r2;
// 也可以用三目運(yùn)算符進(jìn)行騷操作
// r3 -> next = r1 ? r1 : r2;
delete LB;
}到了這里，關(guān)于第21關(guān)：基于鏈表的兩個(gè)遞增有序序列的合并的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
