從LeetCode學演算法 - 4 Linked List (1)

0021. Merge Two Sorted Lists (Easy)

Question

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

分析/解題

題目要求將兩個已排序的linked lists合併，
且所產生的新list必須由原有的節點(node)所構成。

Linked List是一個很常見的資料結構，資料與資料連接的方式是單向的，
通常從第一個節點(node)往後連接到最後一個節點(node)。
每個節點上會存放一個(或一組)資料以及連結(link)，
每個連結會指向到下一個節點 的位置(記憶體位址)。
(在C/C++裡面連結基本上就是指標(pointer))

你可能會問，那麼最後一個節點呢?
最後一個節點除了儲存資料以外，因為連結沒有東西了，所以會給定空值。在演算法的書中一般會稱為NIL ，NIL在英文裡面就是nothing 的意思，
表示沒有任何東西。

在Java中有LinkedList的資料結構，它同樣是List的一種。
但一般遇到題目的時候會給的通常是一個node，
用來指向到該List的第一個節點。

我們會看到如果你打開LeetCode選擇Java時，
上方已經先用註解告訴你這個ListNode的結構了：

1
2
3
4
5
6
7
8
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

也就是說，題目預先定義了一個class叫做ListNode，
val用來存放每個node的值，next用來指向到下一個node ，
有一個ListNode(int x) 的建構子(constructor)，
可以讓你在產生一個新的節點時給定其值。

對於LinkedList來說，它最大的好處在於新增/刪除節點時相當方便。
例如現在有a->b，我想要加一個資料值為20的c節點，放在b後面的話，
以Java而言只需要:

1
2
3
ListNode b = a.next; // 因為一開始我們只知道a的位置而已XD
ListNode c = new ListNode(20);
b.next = c;

如果是插入在a跟b中間呢？也不難，
只是我們要先記住b，不然一旦沒有人記它，它就消失在時空裂縫中了(誤)
(會依照各自編譯器的規範，只是以我們而言是真的就沒辦法找到它了)

1
2
3
4
5
// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
a.next = c;
c.next = b;

請留意如果你調動了一些節點的順序，留意他們的next是否被妥善處理，
該被清空的請給定NIL。在Java中是用null來表示，而Python則是用None。 回到題目，我們該如何去合併排列好的兩個LinkedList呢？
這邊提供一個很簡單的遞迴思路。
(遞迴的概念，我們之後再專門做一篇相關的來講解)
我們合併兩個list的狀況目標還是要呈現排序好的樣子，
那麼怎麼排呢？
由於原先的list已經是排好的，
我們拿出最左邊的node比較，稱為l1跟l2。
l1是全空的狀況下，那其實答案就是l2(因為後面就不用繼續排了)，
反之l2是全空的話，答案就是l1。
那麼如果l1的值小於l2的值的話，那麼l1應該要當頭，
接下來我們要拿l1.next 跟l2 來做比較大小，比較小的，
就會是新的l1連接的下一個節點。
一直連接到最後，我們就可以得到合併好的list了！
相等的狀況因為題目沒有特別要求要分辨是l1還是l2的節點，
所以任取一個均可。

例：
l1: 1 -> 3 -> 5 ->8 ->10, l2: 2 -> 4 -> 4
1先跟2比，1比較小所以當頭(1) ->
3跟2比，2比較小(1->2) ->
3跟4比(1->2->3) ->
5跟4比(1->2->3->4) ->
5跟4比(1->2->3->4->4) ->
l2的部分已經空了，填入l1中5以後剩下的部分
(1->2->3->4->4-> 5 ->8 ->10)

寫成Java的程式如下。

Java:

當然我們也可以用迴圈(迭代)的方法來解，
但這時候我們就要比較仔細的去處理節點間的關係了。
在Python中判斷是否為None可以使用if，
通過if的話節點就代表該節點是有值的，
你也可以加入not的關鍵字來處理你所需要的判斷式。
比如我可以用if not (l1 and l2)來表達其中一個以上是空的狀況，
並回傳不是None的那個node。

操作上，我們需要一個dummy node做為旁觀者，
讓它從頭到尾都只保持在同樣的位置 ，並指向到第一個節點。

接著我們定義一個節點叫做prev，
prev的next 會指定給下一個比較過後較小的那個節點 。
那麼，每次將prev的next拿到以後，
l1或l2(看哪個比較小)就自己遞移到下一個節點 ，
並且prev也往下走到自己的next，準備接取下一個節點；
重覆上面的動作直到其中一邊節點用光 ，
即可把剩下的直接全接到prev.next上。

最終我們回傳的答案是dum.next ，因為只有dum沒有被動過，
其他的節點其實都已經被改動過指向的位址了。

Python

在有關linked list的部分，因為牽扯到位址的概念，
所以操作上要稍微再思考一下，比較不容易搞混。
最重要的是，對於Java和Python來說，由於所使用的都是class來建立node，
所以其實你看到的等號，除了給定val的狀況以外，
其他其實都是在做把右邊放的記憶體位址存到左邊 的動作，
所以指向的記憶體位址變了，代表的節點也就跟著變了 ，務必要留意這點。

面試實際可能會遇到的問題

「請用iterative(迭代或迴圈)/recursive(遞迴)的方式來解」
(上面Java是recursive solution，Python是iterative solution，
讀者可以嘗試改成另一個語言試看看)

「使用遞迴的話會有什麼限制？」
(有可能受到編譯器規範的最大function stack上限限制，
同時，連續的函式呼叫的效率，相對於在迴圈中執行來說會較差)

「那為什麼你會用遞迴？」
(因為遞迴比較好想啊XDDDDD)(別這麼誠實，雖然大家都知道XD)
(因為在一般狀況下，遞迴解通常會較為容易閱讀，
也比較符合人類的思路模式，就像推骨牌一樣，
當起始條件和後續的脈絡定下來以後，後面的結果就會水到渠成。)

「時間複雜度是？」
( worst case是O(N1+N2)，best case是O(min(N1, N2))。)

「如果希望你另外開一個新的linked list，不用原本的節點來解這題呢？」
(這樣會比較簡單，一樣兩兩比較，但改成較小的取其val來產生一個新的ListNode，接在你的新的linked list後面，讀者可以嘗試看看，
別忘記要留dummy node歐！)

從LeetCode學演算法，我們下次見囉，掰~