題目描述

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

方法一：遞歸

（雖然但是，為什么要遞歸?。≌l(shuí)想得到?。。?br>

通過(guò)遞歸，找到不為null的鏈表頭部值較小者

將剩余部分與另一個(gè)鏈表遞歸后鏈到后面

抄來(lái)的代碼：

可以看到，有一個(gè)鏈表是null的情況下，直接return了非空鏈表

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n+m)，其中 n 和 m 分別為兩個(gè)鏈表的長(zhǎng)度。因?yàn)槊看握{(diào)用遞歸都會(huì)去掉 l1 或者 l2 的頭節(jié)點(diǎn)（直到至少有一個(gè)鏈表為空），函數(shù) mergeTwoList 至多只會(huì)遞歸調(diào)用每個(gè)節(jié)點(diǎn)一次。因此，時(shí)間復(fù)雜度取決于合并后的鏈表長(zhǎng)度，即O(n+m)。

空間復(fù)雜度：O(n+m)，其中 n 和 m 分別為兩個(gè)鏈表的長(zhǎng)度。遞歸調(diào)用 mergeTwoLists 函數(shù)時(shí)需要消耗?？臻g，?？臻g的大小取決于遞歸調(diào)用的深度。結(jié)束遞歸調(diào)用時(shí) mergeTwoLists 函數(shù)最多調(diào)用 n+m 次，因此空間復(fù)雜度為 O(n+m)。

方法二：迭代

高大上的名字

其實(shí)就是每次把小的那個(gè)鏈到一個(gè)鏈表上

上代碼：

時(shí)間復(fù)雜度不變，空間復(fù)雜度變?yōu)镺(1)

踩的坑

這道題十分滴簡(jiǎn)單，但是，但是......

如果你調(diào)試的過(guò)程中出現(xiàn)了下面這種情況

就要注意了，看一看

有沒(méi)有挪動(dòng)輸出鏈表的指針

輸出鏈表的指針挪動(dòng)是不是寫(xiě)到了分支條件里

大概，是這樣的......