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

將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(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]

思路

可以簡(jiǎn)單理解為：同時(shí)遍歷兩個(gè)鏈表，當(dāng)前遍歷的結(jié)點(diǎn)，誰(shuí)的結(jié)點(diǎn)小，就把誰(shuí)的結(jié)點(diǎn)“摘下來(lái)”，“安裝”在新鏈表上就可以了吧。

這里為了簡(jiǎn)單方便的處理，給新鏈表先“安裝”一個(gè)頭結(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)的鏈表解決問(wèn)題

//待輸出鏈表的頭部

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

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

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

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

if(l1-vall2-val){

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

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

else{

last-next=l2;

l2=l2-next;

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

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

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

if(l1!=nullptr){

last-next=l1;

elseif(l2!=nullptr){

last-next=l2;

returnhead-next;

鏈表Listnode詳細(xì)介紹

Listnode定義。

structListNode{

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

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

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

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

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

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

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

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

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

3.