輸入兩個(gè)遞增排序的鏈表，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。

示例

• 輸入：1->2->4, 1->3->4

• 輸出：1->1->2->3->4->4

限制

• 0 <= 鏈表長度 <= 1000

方法一：迭代（偽頭節(jié)點(diǎn)）

當(dāng) l1 和 l2 都不是空鏈表時(shí)，判斷 l1 和 l2 哪個(gè)鏈表的節(jié)點(diǎn)值最小，將較小的值的節(jié)點(diǎn)添加到結(jié)果鏈表里，并且將對(duì)應(yīng)的鏈表的節(jié)點(diǎn)向下移一位。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n+m)，其中 n 和 m 分別為兩個(gè)鏈表的長度。因?yàn)槊看窝h(huán)迭代中，l1 和 l2 只有一個(gè)元素會(huì)被放進(jìn)合并鏈表中， 因此 while 循環(huán)的次數(shù)不會(huì)超過兩個(gè)鏈表的長度之和。所有其他操作的時(shí)間復(fù)雜度都是常數(shù)級(jí)別的，因此總的時(shí)間復(fù)雜度為 O(n+m)。

• 空間復(fù)雜度：O(1)。我們只需要在常數(shù)的空間存放若干變量。

方法二：遞歸

兩個(gè)鏈表頭部值較小的一個(gè)節(jié)點(diǎn)與剩下元素的 merge 操作結(jié)果合并。

代碼如下：

復(fù)雜度分析

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

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

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。