今天我們來討論一下如何將兩個鍊表合併的問題。
我們來看一下問題的具體描述：有兩個單向鍊表，它們每個節點都有一個數字，且節點中的數字按照升序排列，現在需要合併這兩個鍊表，合併後仍然是按照升序排列。
舉例如下：
我們最先想到的應該是會用暴力方法來解決這個問題，即將直接將L2鍊表連接到L1鍊表後，形成新的鍊表，然後對新的鍊表進行排序。
雖然這個方法是可行的，但是這個方法並不是最好的，這個方法主要的耗時在於重新排序，它的時間複雜度是O（m+n）log（m+n），m和n分別是L1和L2鍊表的長度，稍後我們會給出更加優雅的方案以供討論。
在提出第二種方案之前，需要提一下可能會用到的一個「工具」——虛擬節點（dummy node），虛擬節點是當我們合併兩個鍊表時不知道哪個節點是新鍊表節點的頭節點時會用到。對於我們之前提到的這個問題，我們會用到兩個指針p1（指向L1頭節點）、p2（指向L2頭節點），前面提到的虛擬節點和當前節點（current node，用於循環，被初始化指向虛擬節點）。通過循環訪問所有節點來構成新的鍊表。在每次循環中，會比較兩個鍊表中p1和p2指向的節點的值，使當前節點一直指向較小值節點的下一節點。如下圖：
在第一步中，p1指向的節點值為2，p2指向節點值為6,2小於6，所以curr指向p1，p1指向下一節點，即指向節點值為5的節點，如下圖：
第二步中，p1指向的節點的值仍然小於p2指向的節點的值，所以繼續向後移動，如下圖：
第三步中，p1指向的節點的值大於p2指向的節點的值，curr指向p2當前指向的節點，p2向後移動，如下圖：
以此類推，直到p1或者p2指針移動到鍊表的末端，因為我們在每次比較中都選擇較小的值，所以當p1或者p2中任何一個指針指向鍊表末端，代表另外一個沒有還沒到達末端的鍊表的後序的值都比已到達末端的鍊表中最大的值要大，所以只需要將後續的節點追加到新的鍊表後即可。代碼如下：
接下來我們介紹一下第三種方法，就是用遞歸的方式解決這個問題。遞歸（recursion）是一種在計算機科學中非常基本且普遍的思考問題的方式。典型的遞歸思路就是可以把問題變為更小的問題，並且這個更小的問題可以繼續遞歸成更小的問題，知道這個問題小到到達一個邊界條件（boundary condition），以至於可以很輕鬆地解決。
在這個問題中，我們的邊界條件很簡單，就是當L2指向了null，返回L1或者L1指向了null，返回L2。如果L1或者L2沒有指向null，就需要比較L1和L2對應的值哪個更小，當有結果以後，這個新的鍊表就更長了，而需要比較的鍊表就更短了，顯然，這樣這個問題就比較之前的簡單了，如此反覆遞歸即可。代碼如下：
為你詳細講解十二個常見算法問題，不僅讓你學會如何掌握這些問題的解題代碼，還會讓你學到解決算法問題所必需的四類解題模板，讓你輕鬆應對各類新問題。↓↓↓