iT邦幫忙

DAY 29
0

連續30天,挑戰演算法系列 第 29

[Day29] 30 天挑戰演算法 - 合併兩個已排序的 List

題目來源Merge Two Sorted Lists

問題:
請將兩個已經排序過的 Linked List 合併成一個新的 Linked List 回傳。

例子
L1 = {1, 2, 4, 7, 8}
L2 = {5}
請回傳 {1, 2, 4, 5, 7, 8}

想法
既然題目給予的兩個 Linked List 已經排序過了,所以在合併的過程中我們只要依序兩兩相比,將較小的那個加入到新的 Linked List 即可。因此,只剩下以下三件事情需要考慮而已:

  1. L1, L2 都為 Null 時
  2. L1 為 Null 時
  3. L2 為 Null 時

一開始先處理 L1 或 L2 為 Null 的狀況:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null && l2 == null)
        return null;
    else if (l1 != null && l2 == null)
        return l1;
    else if (l1 == null && l2 != null)
        return l2;
...(略)
}

接下來,宣告一個新的節點用來指向新的 Linked List, 並且判斷 L1, L2 節點,將值較小的那個給予這個節點。

...(略)
ListNode head = null;
if (l1.val < l2.val){
    head = new ListNode(l1.val);
    l1 = l1.next;
} else{
    head = new ListNode(l2.val);
    l2 = l2.next;
}
...(略)        

最後,再宣告一個指標節點,開始針對 L1 和 L2 的每個節點兩兩相比,加入新的 ListNode

...(略)

ListNode node = head;        
while(l1 != null || l2 != null) {
    // l1, l2 都不是 null, 並且 l1 較小
    if (l1 != null && l2 != null && l1.val < l2.val) {
        node.next = new ListNode(l1.val);
        l1 = l1.next;
    // l1, l2 都不是 null, 並且 l2 較小
    } else if (l1 != null && l2 != null && l1.val > l2.val ) {
        node.next = new ListNode(l2.val);
        l2 = l2.next;
    // l2 不是 null ( l1 為 null)
    } else if (l2 != null) {
        node.next = new ListNode(l2.val);
        l2 = l2.next;
    // l1 不為 null (l2 是 null)
    } else if (l1 != null) {
        node.next = new ListNode(l1.val);
        l1 = l1.next;
    }
    node = node.next;
}
    
return head;

雖然完成了,不過程式碼還是很醜!
仔細看一下,上面有四個判斷式,不過只有兩種動作,第一個動作是

node.next = new ListNode(l1.val);
l1 = l1.next;

第二個動作是

node.next = new ListNode(l2.val);
l2 = l2.next;

而這四個動作只是要判斷,到底要用 L1 的值還是用 L2 的值而已。所以我們可以根據上面的解答重新來思考一下,要怎麼樣才能在修正一下我們的判斷式。
什麼情況會用 L1 的值呢?有兩個:

  1. L2 已經沒有節點了(也就是等於 Null)
  2. L2 的值大於 L1

好,我們先假設只有這兩種狀況才會用 L1 的值,那其他狀況一定都是用 L2 了。
我們就先來修改一下判斷式,再利用 Test Case 來驗證我們的想法對不對:

if ( l2 == null || l1 != null && l2.val > l1.val) {
    node.next = new ListNode(l1.val);
    l1 = l1.next;
} else {
    node.next = new ListNode(l2.val);
    l2 = l2.next;
}
node = node.next;

一驗證之下發現!果然我們的想法是對的!這樣一來,兩兩相比的邏輯判斷式就變得精簡許多了!


上一篇
[Day28] 30 天挑戰演算法 - 驗證括號
下一篇
[Day30] 30 天挑戰演算法 - 判斷循環的LinkedList
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言