- 假設(shè)有兩個(gè)元素值按遞增次序排列的線性表，均以單鏈表形式存儲(chǔ)打却，編寫算法將這兩個(gè)單鏈表歸并為一個(gè)按元素值遞減次序排列的單鏈表鸠匀，并要求利用原來(lái)兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。
（考慮到使用遞減排列洒试，故使用頭插法）
void unionDesc(linkList L1, linkList L2) {
linkList p1 = L1->pNext, p2 = L2->pNext;
linkList temp = nullptr;
L1->pNext = nullptr; //任選其中一個(gè)鏈表的頭部作為頭指針
while (p1 && p2) {
if (p1->data <= p2->data) {
temp = p1->pNext;
p1->pNext = L1->pNext;
L1->pNext = p1;
p1 = temp; //上述為頭插的基本操作，需要熟練掌握
}
else {
temp = p2->pNext;
p2->pNext = L1->pNext;
L1->pNext = p2;
p2 = temp;
}
}
if (p1) {
p2 = p1;
}
while (p2) {
temp = p2->pNext;
p2->pNext = L1->pNext;
L1->pNext = p2;
p2 = temp;
}
free(L2);
}
- 設(shè)A和B是兩個(gè)單鏈表（帶頭結(jié)點(diǎn)）朴上，其中元素遞增有序垒棋，設(shè)計(jì)一個(gè)算法從A和B公共元素中產(chǎn)生單鏈表C，要求不破壞A,B的結(jié)點(diǎn)痪宰。
注意要設(shè)置變量temp叼架，始終指向新鏈表的尾部畔裕。貌似沒(méi)啥難度吧。
linkList commonNodeList(linkList L1, linkList L2) {
linkList p1 = L1->pNext, p2 = L2->pNext;
linkList c = (linkList)malloc(sizeof(Node));
linkList temp = c, t;
while (p1 && p2) {
if ( p1->data < p2->data ) {
p1 = p1->pNext;
}
else if (p2->data < p1->data) {
p2 = p2->pNext;
}
else {
t = (linkList)malloc(sizeof(Node));
t->data = p1->data;
temp->pNext = t;
temp = temp->pNext;
p1 = p1->pNext;
p2 = p2->pNext;
}
}
temp->pNext = nullptr;
return c;
}
- 已知兩個(gè)鏈表A和B分別表示兩個(gè)集合乖订，元素遞增排列扮饶，編制函數(shù)，求A和B的交集乍构，并存放于A鏈表中甜无。（這一題和上一題的主要區(qū)別是，本題結(jié)果保留在原來(lái)的鏈表上哥遮，鏈表的其余部分需要進(jìn)行釋放发绢。）
void intersection(linkList &L1, linkList &L2) {
linkList p1 = L1->pNext, p2 = L2->pNext, temp = L1;
while (p1 && p2) {
if (p1->data == p2->data) {
temp->pNext = p1;
temp = temp->pNext;
linkList tNode = p2;
p1 = p1->pNext;
p2 = p2->pNext;
free(tNode);//將不用的L2上的結(jié)點(diǎn)釋放
}
else if (p1->data < p2->data) {
linkList tNode = p1;
p1 = p1->pNext;
free(tNode);
}
else {
linkList tNode = p2;
p2 = p2->pNext;
free(tNode);
}
}
while (p1) {
linkList tNode = p1;
p1 = p1->pNext;
free(tNode);
}
while (p2) {
linkList tNode = p2;
p2 = p2->pNext;
free(tNode);
}
temp->pNext = nullptr;
free(L2);
}
- 兩個(gè)整數(shù)序列棠赛，A和B，已經(jīng)存入兩個(gè)單鏈表中，設(shè)計(jì)算法判斷B是否是A的連續(xù)子序列此再。
bool isSubsquence(linkList l1, linkList l2) {
linkList p1 = l1->pNext, p2 = l2->pNext;
while (p1 && p2) {
if (p1->data == p2->data) {
p1 = p1->pNext;
p2 = p2->pNext;
}
else {
p1 = p1->pNext;
p2 = l2->pNext;
}
}
if (p2 == nullptr) return 1;
else return 0;
}
后面瑣碎待補(bǔ)较屿。
