C++實現(xiàn)合并兩個排序的鏈表
更新時間：2019年03月03日 14:40:21 作者：francis_xd
這篇文章主要為大家詳細介紹了C++實現(xiàn)合并兩個排序的鏈表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文實例為大家分享了C++合并兩個排序的鏈表，供大家參考，具體內(nèi)容如下
問題描述
輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
方法一
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* newList = NULL; //新鏈表頭
ListNode* newListRear = NULL; //新鏈表尾
// 先處理某個鏈表為空的情形
if (pHead1 == NULL){
return pHead2;
}
if (pHead2 == NULL){
return pHead1;
}
// 把數(shù)值小的結(jié)點放入新鏈表，生成頭節(jié)點
if (pHead1->val <= pHead2->val){
newList = pHead1;
newListRear = pHead1;
pHead1 = pHead1->next;
}else{
newList = pHead2 ;
newListRear = pHead2;
pHead2 = pHead2->next;
}
// 兩表均不空的情形下，遍歷
while (pHead1 != NULL && pHead2 != NULL) {
if (pHead1->val <= pHead2->val) {
newListRear->next =pHead1;
newListRear = pHead1;
pHead1 = pHead1->next;
}else{
newListRear->next =pHead2;
newListRear = pHead2;
pHead2 = pHead2->next;
}
}
//某一表為空時，把另一表接入新表表尾
if (pHead1 == NULL) {
newListRear->next = pHead2;
}
if (pHead2 == NULL) {
newListRear->next = pHead1;
}
return newList;
}
};
方法二（遞歸思想）
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == NULL){
return pHead2;
}
if (pHead2 == NULL){
return pHead1;
}
if (pHead1->val <= pHead2->val){ // pHead1為合并后的頭節(jié)點
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}else{ // pHead2 為合并后的頭節(jié)點
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
};
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
探討C++中不能聲明為虛函數(shù)的有哪些函數(shù)
下面小編就為大家?guī)硪黄接慍++中不能聲明為虛函數(shù)的有哪些函數(shù)。希望對大家有所幫助。一起跟隨小編過來看看吧，祝大家游戲愉快哦2017-01-01
Linux C/C++實現(xiàn)DNS客戶端請求域名IP的示例代碼
DNS全稱：Domain Name System,域名解析系統(tǒng),是互聯(lián)網(wǎng)的一項服務(wù),本文主要介紹了C/C++如何實現(xiàn)DNS客戶端請求域名IP,感興趣的可以了解下2024-03-03
這篇文章主要介紹了C++中STL容器的主要使用及含義說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
抽象類(abstract class)和接口(interface)的概念是面向?qū)ο笤O(shè)計中常用的概念, 也是比較容易混淆的概念. 在這里, 我提出一種區(qū)分它們的思路2013-04-04
這篇文章主要介紹了C++中按引用傳遞參數(shù)的好處有哪些,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
C++?Stack（堆棧）?是一個容器類的改編，為程序員提供了堆棧的全部功能，也就是說實現(xiàn)了一個先進后出（FILO）的數(shù)據(jù)結(jié)構(gòu)，許多程序都使用了?queue?容器。queue?容器可以用來表示超市的結(jié)賬隊列或服務(wù)器上等待執(zhí)行的數(shù)據(jù)庫事務(wù)隊列2022-03-03
這篇文章主要介紹了C++?右值引用，右值引用指的是以引用傳遞（而非值傳遞）的方式使用?C++?右值，下面文章將對此詳細介紹,需要的朋友可以參考一下，希望對你有所幫助2021-12-12
C++與QML進行數(shù)據(jù)交互的常見方法總結(jié)
這篇文章主要為大家詳細介紹了C++與QML進行數(shù)據(jù)交互的常見方法,文中 的示例代碼講解詳細,具有一定的參考價值,有需要的小伙伴可以跟隨小編一起了解一下2023-10-10
這篇文章主要介紹了C++嵌入式內(nèi)存管理，是對上一篇內(nèi)存的一個補充，主要講解Linux中的內(nèi)存；這部分對于一些端側(cè)部署的伙伴來說比較重要，推薦針對不同的板子，下面來看看詳細內(nèi)容吧,需要的朋友可以參考一下2021-12-12
本文主要介紹了C++實現(xiàn)STL容器的示例，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-02-02