帶你了解如何用C++合并兩個有序鏈表
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
示例 1:
輸入:l1 = [1,2,4], l2 = [1,3,4]
輸出:[1,1,2,3,4,4]
示例 2:
輸入:l1 = [], l2 = []
輸出:[]
示例 3:
輸入:l1 = [], l2 = [0]
輸出:[0]
思路
可以簡單理解為: 同時遍歷兩個鏈表, 當(dāng)前遍歷的結(jié)點,誰的結(jié)點小,就把誰的結(jié)點“摘下來”,“安裝”在新鏈表上就可以了吧。
這里為了簡單方便的處理, 給新鏈表先“安裝”一個頭結(jié)點
代碼
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 使用帶頭結(jié)點的鏈表解決問題 // 待輸出鏈表的頭部 ListNode* head = new ListNode; //節(jié)點是個指針,需要new來開辟空間 // 待輸出鏈表的 last 結(jié)點 ListNode* last = head; //last和head是一個東西,只是為了最后輸出的時候找到head while(l1 != nullptr && l2 != nullptr){ //循環(huán)條件 if(l1->val < l2->val){ last->next = l1; //last->next指向l1 l1 = l1->next; //將l1的下一個節(jié)點改為l1 } else{ last->next = l2; l2 = l2->next; } last = last->next; //將last的下一個節(jié)點改為last } // l1 或 l2 可能還有剩余結(jié)點沒有合并, // 由于從上面的 while 循環(huán)中退出, 那么鏈表 l1 和 l2 至少有一個已經(jīng)遍歷結(jié)束 if(l1 != nullptr){ last->next = l1; } else if(l2 != nullptr){ last->next = l2; } return head->next; } };
鏈表Listnode詳細(xì)介紹
Listnode定義 。
struct ListNode { int val; //定義val變量值,存儲節(jié)點值 struct ListNode *next; //定義next指針,指向下一個節(jié)點,維持節(jié)點連接 }
1.節(jié)點存儲了兩個變量:value 和 next。
value 是這個節(jié)點的值,
next 是指向下一節(jié)點的指針,
當(dāng) next 為空指針時,這個節(jié)點是鏈表的最后一個節(jié)點。
2.注意val只代表當(dāng)前指針的值,
比如p->val表示p指針的指向的值;
而p->next表示鏈表下一個節(jié)點,也是一個指針。
3.構(gòu)造函數(shù)包含兩個參數(shù) _value 和 _next ,分別用來給節(jié)點賦值和指定下一節(jié)點
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
C語言數(shù)據(jù)結(jié)構(gòu)之算法的時間復(fù)雜度
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之算法的時間復(fù)雜度,文章基于c語言的相關(guān)資料展開詳細(xì)介紹,具有一定的參價值,需要的小伙伴可以參考一下2022-05-05VC中CWinThread類以及和createthread API的區(qū)別分析
這篇文章主要介紹了VC中CWinThread類以及和createthread API的區(qū)別分析,較為詳細(xì)的講述了CWinThread類的原理,并以實例形式對AfxBeginThread函數(shù)的內(nèi)部實現(xiàn)進行了解釋說明,需要的朋友可以參考下2014-10-10Qt?QGraphicsItem?移動時出現(xiàn)殘影問題記錄
自定義QGraphicsItem時,繪制rect,對象移動時出現(xiàn)殘影的問題記錄,本文給大家介紹Qt?QGraphicsItem?移動時出現(xiàn)殘影問題記錄,感興趣的朋友跟隨小編一起看看吧2024-06-06C++中常見容器類的使用方法詳解(vector/deque/map/set)
C++中常見的容器類有vector、list、deque、map、set、unordered_map和unordered_set。下面將舉例直接說明各個容器的使用方法,希望對大家有所幫助2023-03-03