帶你了解如何用C++合并兩個有序鏈表

第帶你了解如何用C++合并兩個有序鏈表目錄將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。思路代碼鏈表Listnode詳細(xì)介紹總結(jié)

將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。

示例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é)點(diǎn)，誰的結(jié)點(diǎn)小，就把誰的結(jié)點(diǎn)“摘下來”，“安裝”在新鏈表上就可以了吧。

這里為了簡單方便的處理，給新鏈表先“安裝”一個頭結(jié)點(diǎn)

代碼

*Definitionforsingly-linkedlist.

*structListNode{

*intval;

*ListNode*next;

*ListNode():val(0),next(nullptr){}

*ListNode(intx):val(x),next(nullptr){}

*ListNode(intx,ListNode*next):val(x),next(next){}

*};

classSolution{

public:

ListNode*mergeTwoLists(ListNode*l1,ListNode*l2){

//使用帶頭結(jié)點(diǎn)的鏈表解決問題

//待輸出鏈表的頭部

ListNode*head=newListNode;//節(jié)點(diǎn)是個指針，需要new來開辟空間

//待輸出鏈表的last結(jié)點(diǎn)

ListNode*last=head;//last和head是一個東西，只是為了最后輸出的時候找到head

while(l1!=nullptrl2!=nullptr){//循環(huán)條件

if(l1-vall2-val){

last-next=l1;//last-next指向l1

l1=l1-next;//將l1的下一個節(jié)點(diǎn)改為l1

else{

last-next=l2;

l2=l2-next;

last=last-next;//將last的下一個節(jié)點(diǎn)改為last

//l1或l2可能還有剩余結(jié)點(diǎn)沒有合并，

//由于從上面的while循環(huán)中退出，那么鏈表l1和l2至少有一個已經(jīng)遍歷結(jié)束

if(l1!=nullptr){

last-next=l1;

elseif(l2!=nullptr){

last-next=l2;

returnhead-next;

鏈表Listnode詳細(xì)介紹

Listnode定義。

structListNode{

intval;//定義val變量值，存儲節(jié)點(diǎn)值

structListNode*next;//定義next指針，指向下一個節(jié)點(diǎn)，維持節(jié)點(diǎn)連接

1.節(jié)點(diǎn)存儲了兩個變量：value和next。

value是這個節(jié)點(diǎn)的值，

next是指向下一節(jié)點(diǎn)的指針，

當(dāng)next為空指針時，這個節(jié)點(diǎn)是鏈表的最后一個節(jié)點(diǎn)。

2.注意val只代表當(dāng)前指針的值，

比如p-val表示p指針的指向的值；

而p-next表示鏈表下一個節(jié)點(diǎn)，也是一個指針。

3.