iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 5
2
Software Development

從LeetCode學演算法系列 第 5

[Day 5] 從LeetCode學演算法 - 0021. Merge Two Sorted Lists (Easy)

目標:
這題主要目的在於引導讀者了解Linked List的資料結構以及基本操作。

原題:

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:
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的結構了:

/**
 * 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而言只需要:

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

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

// 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:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

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

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

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

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

Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dum = ListNode(None)
        prev = dum
        
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            prev = prev.next
        
        if l1 == None:
            prev.next = l2
        elif l2 == None:
            prev.next = l1
        
        return dum.next

在有關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學演算法,我們下次見囉,掰~

下篇預告:
0026. Remove Duplicates from Sorted Array (Easy)


上一篇
[Day 4] 從LeetCode學演算法 - 0015. 3Sum (Medium)
下一篇
[Day 6] 從LeetCode學演算法 - 0026. Remove Duplicates from Sorted Array (Easy)
系列文
從LeetCode學演算法30

1 則留言

0
hyj1116
iT邦新手 4 級 ‧ 2019-10-03 23:03:19

你好,請問這段code:
// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
a.next = c;
c.next = b;

似乎應該是:
// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
c.next = b;
a.next = c;
不然b可能就消失在時空裂縫了?

Desolve iT邦新手 5 級‧ 2019-10-04 00:34:20 檢舉

你好:
在理解next這件事情的時候,必須要知道一點是,
以物件而言,它所記錄或指向的都是該物件的記憶體位置,
而非整個值。
以Python而言,我們嘗試定義以下的ListNode,
並給定a, a.next, c,你可以試試看基本的直譯器,
來輸出ListNode的記憶體位置和其val:

>>> class ListNode:
...   def __init__(self, x):
...     self.val = x
...     self.next = None
...
>>> a = ListNode(1)
>>> a.next = ListNode(3)
>>> b = a.next
>>> c = ListNode(20)
>>> a
<__main__.ListNode object at 0x0000000002838DA0>
>>> a, a.val
(<__main__.ListNode object at 0x0000000002838DA0>, 1)
>>> a.next, a.next.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> b, b.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> c, c.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>>
>>> a.next = c
>>> c.next = b
>>> b, b.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> c, c.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>> a.next, a.next.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>> c.next, c.next.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>>

從上面來看,你會發現先做a.next = c而不是c.next = b的結果,
並不會讓b消失在時空裂縫。為什麼呢?

當我們在下a.next = c時,
我們所指涉的是
「將a.next的記憶體位址設定為c的記憶體位址」
此時,由於我們先前已經有變數b來記錄b所在的記憶體位址,
所以這一行並不會讓b記錄的記憶體位置改變,
改變的只有a.next,b並沒有改變。

唯一會讓b找不到的狀況就是我們沒有宣告任何物件來存放這個物件。
類似:

a = ListNode(1)
a.next = ListNode(3) # 也就是b,但我們沒有宣告b來存
c = ListNode(20)
a.next = c # 將a的next指向到c的記憶體位址
# 這時候因為沒有人存ListNode(3),所以它就再也存取不到了!

所以以這個簡短範例而言,
兩者的代換前後順序,並不會影響結果,
也不會有任何人陷入時空裂縫XD

我要留言

立即登入留言