?？途W(wǎng)高頻算法題系列-BM4-合并兩個排序的鏈表

題目描述

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

• 數(shù)據(jù)范圍： 0 <= n <= 1000，-1000 <= 節(jié)點(diǎn)值 <= 1000

• 要求：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(n)

原題目見：BM4 合并兩個排序的鏈表

解法一：鏈表遍歷

• 首先，判斷特殊情況，如果鏈表一為空，直接返回鏈表二；如果鏈表二為空，直接返回鏈表一。

• 否則，先聲明一個新的假頭結(jié)點(diǎn)，然后遍歷鏈表一和鏈表二，過程如下：

• 如果鏈表一為空，直接將鏈表二剩下的結(jié)點(diǎn)接到后面，并終止遍歷

• 如果鏈表二為空，直接將鏈表一剩下的結(jié)點(diǎn)接到后面，并終止遍歷

• 否則，比較鏈表一和鏈表二當(dāng)前結(jié)點(diǎn)的大小，來判斷下一個結(jié)點(diǎn)，然后處理下一個結(jié)點(diǎn)

• 最后，返回合并后的鏈表。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅(jiān)持的力量！