題目描述
輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。
這道題我的第一思路這樣的：可以先周遊這兩個排序的連結清單，把周遊的結果存放在一個集合中，然後調用庫函數arrays.sort方法完成排序，之後，根據這些排好序的結果重新建立一個連結清單，即為合并之後但仍然排序的連結清單。但是這種思路需要額外的list和建立連結清單的空間開銷，而且時間複雜度最快也是o(nlogn)。是以不是很理想。第二種思路是這樣的：因為兩個連結清單都是排序的，是以可以先比較兩個連結清單的頭結點，這樣就确定了合并之後連結清單的第一個節點，之後再比較兩個連結清單的第二個節點（原來較大值與較小值所屬連結清單的第二個節點進行比較），這樣依次就能确定合并連結清單的第二個、第三個節點，故明顯是一個遞歸的過程。參照這個過程實作代碼如下（已被牛客ac）：
上面的遞歸代碼看起來很簡潔，但是非遞歸代碼也是需要掌握的，代碼如下：