目錄

第1題 合并兩個(gè)非遞減有序鏈表

得分點(diǎn)（必背）

題解

函數(shù)聲明與初始化變量：

初始化合并鏈表的頭節(jié)點(diǎn)：

合并兩個(gè)鏈表：

處理剩余節(jié)點(diǎn)：

返回合并后的鏈表：

完整測(cè)試代碼

---

🌈 嗨，我是命運(yùn)之光！

🌌 2024，每日百字，記錄時(shí)光，感謝有你，攜手前行~

🚀 攜手啟航，我們一同深入未知的領(lǐng)域，挖掘潛能，讓每一步成長(zhǎng)都充滿(mǎn)意義。

---

第1題 合并兩個(gè)非遞減有序鏈表

已知帶頭節(jié)點(diǎn)的單鏈表 LA 和 LB ，其元素均為非遞減有序排列，編寫(xiě)算法利用原表結(jié)點(diǎn)空間，將鏈表 LA 和 LB 合并為非遞減有序序列的單鏈表 LC

得分點(diǎn)（必背）

// 合并兩個(gè)非遞減有序鏈表（得分點(diǎn)）
LinkList mergeLists(LinkList lista, LinkList listb){LinkList listc, p = lista, q = listb, r;
//listc指向lista 和 listb所指結(jié)點(diǎn)中較小者
//初始化合并鏈表的頭節(jié)點(diǎn)if(lista->data<=listb->data){listc=lista;r=lista;p=lista->next;}else{listc=listb;r=listb;q=listb->next;}
//合并兩個(gè)鏈表while(p!=NULL && q!=NULL){if(p->data<=q->data){r->next=p;r=p;p=p->next;}else{r->next=q;r=q;q=q->next;}}r->next=(p!=NULL)?p:q; //處理剩余節(jié)點(diǎn)return listc; //返回合并后的鏈表
}

題解

這段代碼的功能是將兩個(gè)非遞減有序鏈表合并成一個(gè)非遞減有序鏈表。下面我將逐步解釋這段代碼：

函數(shù)聲明與初始化變量：

LinkList mergeLists(LinkList lista, LinkList listb){LinkList listc, p = lista, q = listb, r;

• LinkList mergeLists(LinkList lista, LinkList listb)：函數(shù)名為mergeLists，參數(shù)是兩個(gè)非遞減有序鏈表lista和listb，返回值是合并后的鏈表。
• LinkList listc, p = lista, q = listb, r;：定義了四個(gè)指針變量：
  • listc：用于指向合并后的鏈表的頭節(jié)點(diǎn)。
  • p：初始化為指向鏈表lista的當(dāng)前節(jié)點(diǎn)。
  • q：初始化為指向鏈表listb的當(dāng)前節(jié)點(diǎn)。
  • r：用于構(gòu)建合并后的鏈表。

初始化合并鏈表的頭節(jié)點(diǎn)：

if(lista->data<=listb->data){listc=lista;r=lista;p=lista->next;
}
else{listc=listb;r=listb;q=listb->next;
}

if(lista->data<=listb->data)：比較lista和listb的頭節(jié)點(diǎn)數(shù)據(jù)。

• 如果lista的頭節(jié)點(diǎn)數(shù)據(jù)小于等于listb的頭節(jié)點(diǎn)數(shù)據(jù)：
  • listc = lista：將合并鏈表的頭節(jié)點(diǎn)指向lista的頭節(jié)點(diǎn)。
  • r = lista：r指向當(dāng)前合并鏈表的最后一個(gè)節(jié)點(diǎn)（此時(shí)是lista的頭節(jié)點(diǎn)）。
  • p = lista->next：將指針p移動(dòng)到lista的下一個(gè)節(jié)點(diǎn)。
• 否則：
  • listc = listb：將合并鏈表的頭節(jié)點(diǎn)指向listb的頭節(jié)點(diǎn)。
  • r = listb：r指向當(dāng)前合并鏈表的最后一個(gè)節(jié)點(diǎn)（此時(shí)是listb的頭節(jié)點(diǎn)）。
  • q = listb->next：將指針q移動(dòng)到listb的下一個(gè)節(jié)點(diǎn)。

合并兩個(gè)鏈表：

while(p!=NULL && q!=NULL){if(p->data<=q->data){r->next=p;r=p;p=p->next;}else{r->next=q;r=q;q=q->next;}
}

while(p!=NULL && q!=NULL)：循環(huán)遍歷lista和listb，直到其中一個(gè)鏈表遍歷完（p或q變?yōu)?code>NULL）。

• if(p->data<=q->data)：比較p和q指向的節(jié)點(diǎn)數(shù)據(jù)。
  • 如果p的數(shù)據(jù)小于等于q的數(shù)據(jù)：
    • r->next=p：將當(dāng)前合并鏈表的最后一個(gè)節(jié)點(diǎn)的next指針指向p。
    • r=p：將r指向p，即更新當(dāng)前合并鏈表的最后一個(gè)節(jié)點(diǎn)。
    • p=p->next：將指針p移動(dòng)到lista的下一個(gè)節(jié)點(diǎn)。
  • 否則：
    • r->next=q：將當(dāng)前合并鏈表的最后一個(gè)節(jié)點(diǎn)的next指針指向q。
    • r=q：將r指向q，即更新當(dāng)前合并鏈表的最后一個(gè)節(jié)點(diǎn)。
    • q=q->next：將指針q移動(dòng)到listb的下一個(gè)節(jié)點(diǎn)。

處理剩余節(jié)點(diǎn)：

r->next=(p!=NULL)?p:q;

r->next=(p!=NULL)?p:q;：當(dāng)while循環(huán)結(jié)束時(shí)，可能還剩下一個(gè)鏈表中有未處理完的節(jié)點(diǎn)。

• 如果p不為空，則將r->next指向p，即將剩余的lista節(jié)點(diǎn)連接到合并鏈表的末尾。
• 如果p為空，則將r->next指向q，即將剩余的listb節(jié)點(diǎn)連接到合并鏈表的末尾。

返回合并后的鏈表：

return listc;

• return listc;：返回合并后的鏈表listc。

總結(jié)：這段代碼通過(guò)比較兩個(gè)鏈表的節(jié)點(diǎn)數(shù)據(jù)，將較小的數(shù)據(jù)節(jié)點(diǎn)依次連接到合并后的鏈表中，最終返回一個(gè)合并后的非遞減有序鏈表。

完整測(cè)試代碼

#include<iostream>
using namespace std;// 定義鏈表節(jié)點(diǎn)結(jié)構(gòu)
struct Node {
int data;
Node* next;
};
// 定義 LinkList 類(lèi)型為指向 Node 的指針
typedef Node* LinkList;
// 初始化鏈表
void InitList(LinkList& L){L=new Node;L->next=NULL;
}
// 合并兩個(gè)非遞減有序鏈表（得分點(diǎn)）
LinkList mergeLists(LinkList lista, LinkList listb){LinkList listc, p = lista, q = listb, r;//lilistc指向lista 和 listb所指結(jié)點(diǎn)中較小者if(lista->data<=listb->data){listc=lista;r=lista;p=lista->next;}else{listc=listb;r=listb;q=listb->next;}while(p!=NULL && q!=NULL){if(p->data<=q->data){r->next=p;r=p;p=p->next;}else{r->next=q;r=q;q=q->next;}}r->next=(p!=NULL)?p:q;return listc;
}
// 打印鏈表
void printList(LinkList head) {while (head != nullptr) {cout << head->data << " ";head = head->next;}cout << endl;
}int main() {// 創(chuàng)建鏈表 a: 1 -> 3 -> 5Node* a1 = new Node{1, nullptr};Node* a2 = new Node{3, nullptr};Node* a3 = new Node{5, nullptr};a1->next = a2;a2->next = a3;// 創(chuàng)建鏈表 b: 2 -> 4 -> 6Node* b1 = new Node{2, nullptr};Node* b2 = new Node{4, nullptr};Node* b3 = new Node{6, nullptr};b1->next = b2;b2->next = b3;// 合并鏈表LinkList mergedList = mergeLists(a1, b1);// 打印結(jié)果printList(mergedList); // 應(yīng)該輸出: 1 2 3 4 5 6// 清理內(nèi)存while (mergedList != nullptr) {Node* temp = mergedList;mergedList = mergedList->next;delete temp;}return 0;
}

---

嗨，我是命運(yùn)之光。如果你覺(jué)得我的分享有價(jià)值，不妨通過(guò)以下方式表達(dá)你的支持：👍 點(diǎn)贊來(lái)表達(dá)你的喜愛(ài)，📁 關(guān)注以獲取我的最新消息，💬 評(píng)論與我交流你的見(jiàn)解。我會(huì)繼續(xù)努力，為你帶來(lái)更多精彩和實(shí)用的內(nèi)容。

點(diǎn)擊這里👉 ，獲取最新動(dòng)態(tài)，?? 讓信息傳遞更加迅速。