C++解決合并兩個排序的鏈表問題
更新時間：2021年12月07日 14:18:52 作者：翟天保Steven
本文主要介紹了通過C++解決合并兩個排序的鏈表并使新鏈表中的節(jié)點仍然是遞增排序的。文中代碼講解詳細，有需要的朋友可以參考一下
題目描述：
輸入兩個遞增的鏈表，單個鏈表的長度為n，合并這兩個鏈表并使新鏈表中的節(jié)點仍然是遞增排序的。
數(shù)據(jù)范圍： n為0~1000，節(jié)點值為-1000~1000
要求：空間復雜度 O(1)，時間復雜度 O(n)
如輸入{1,3,5},{2,4,6}時，合并后的鏈表為{1,2,3,4,5,6}，所以對應的輸出為{1,2,3,4,5,6}，轉換過程如下圖所示：
或輸入{-1,2,4},{1,3,4}時，合并后的鏈表為{-1,1,2,3,4,4}，所以對應的輸出為{-1,1,2,3,4,4}，轉換過程如下圖所示：
示例：
輸入：
{1,3,5},{2,4,6}
返回值：
{1,2,3,4,5,6}
解題思路：
本題考察數(shù)據(jù)結構鏈表的使用。有兩種解法：
- 遍歷比較。建立一個新的頭節(jié)點head后，用cur指針指向下一節(jié)點；然后依次比較兩個子鏈表節(jié)點的值大小，誰小先塞誰，塞完就將其指向下一個節(jié)點；直到某個子鏈表遍歷完，將cur的next指向沒遍歷完的那個鏈表當前的節(jié)點。
- 遞歸。從pHead1和pHead2的頭節(jié)點開始比較，誰小就返回誰，然后其下一個指向，指向Merge函數(shù)的結果，Merge輸入的兩個鏈表為小的一方的next和大的一方的頭節(jié)點，也就是用下一個值和它繼續(xù)比誰更??；依次類推，遞歸中斷的標志是有其中一個子鏈表指向nullptr，返回另一方即可。
測試代碼：
解法一，遍歷：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode *head=new ListNode(-1);
ListNode *cur=head;
while(pHead1&&pHead2)
{
if(pHead1->val<=pHead2->val)
{
cur->next=pHead1;
pHead1=pHead1->next;
}
else{
cur->next=pHead2;
pHead2=pHead2->next;
}
cur=cur->next;
}
cur->next=pHead1?pHead1:pHead2;
return head->next;
}
};
解法二，遞歸：??
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if(!pHead1)
return pHead2;
if(!pHead2)
return pHead1;
if(pHead1->val<=pHead2->val)
{
pHead1->next=Merge(pHead1->next,pHead2);
return pHead1;
}
else{
pHead2->next=Merge(pHead1,pHead2->next);
return pHead2;
}
}
};
到此這篇關于C++解決合并兩個排序的鏈表問題的文章就介紹到這了,更多相關C++ 合并兩個排序的鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
利用全局鉤子制作一個個性化的dota游戲改鍵功能，大家可以參考使用2013-11-11
這篇文章主要介紹了C++讀取配置文件的示例代碼，幫助大家更好的理解和學習C++開發(fā)，感興趣的朋友可以了解下2020-08-08
C++ 數(shù)據(jù)結構之kmp算法中的求Next()函數(shù)的算法
這篇文章主要介紹了C++ 數(shù)據(jù)結構之kmp算法中的求Next()函數(shù)的算法的相關資料,需要的朋友可以參考下2017-06-06
用VC++6.0的控制臺實現(xiàn)2048小游戲的程序
本文是作者拜讀劉地同學的《C語言控制臺版2048》之后感覺非常不錯，添加了注釋之后分享給大家的，方便更多的初學者閱讀學習，有需要的小伙伴參考下。2015-03-03
strcat是連接字符串的函數(shù)。函數(shù)返回指針，兩個參數(shù)都是指針，第一個參數(shù)所指向的內(nèi)存的地址必須能容納兩個字符串連接后的大小。2015-09-09
這篇文章主要為大家詳細介紹了基于C語言實現(xiàn)2048游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
這篇文章主要介紹了C/C++ ip地址與int類型的轉換實例詳解的相關資料,這里提供了實例代碼，實現(xiàn)思路及實現(xiàn)方法，需要的朋友可以參考下2016-12-12
C語言使用mciSendString實現(xiàn)播放音樂功能
mciSendString?支持?mp3、wma、wav、mid?等多種媒體格式，使用非常簡單。這篇文章就來為大家介紹一下C語言如何使用mciSendString實現(xiàn)播放音樂功能，需要的可以參考一下2023-02-02
線段樹在一些acm題目中經(jīng)常見到,這種數(shù)據(jù)結構主要應用在計算幾何和地理信息系統(tǒng)中,這篇文章主要給大家介紹了關于線段樹以及C++實現(xiàn)的相關資料,需要的朋友可以參考下2021-07-07
簡述C語言中system()函數(shù)與vfork()函數(shù)的使用方法
這篇文章主要介紹了簡述C語言中system()函數(shù)與vfork()函數(shù)的使用方法,是C語言入門學習中的基礎知識,需要的朋友可以參考下2015-08-08