LeetCode 21. Merge Two Sorted Lists (Easy)
題目連結
https://leetcode.com/problems/merge-two-sorted-lists/
解法 1:迭代法
解題技巧
- Dummy Node (虛擬節點): Dummy Node 代表不包含任何實際數據的節點，通常用在處理 linked list 的問題。在這題使用 dummyNode 當作頭節點，就不用特別處理頭節點的問題。
程式碼
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let dummyNode = new ListNode();
let current = dummyNode;
while (list1 && list2) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
if (list1 !== null) {
current.next = list1;
} else {
current.next = list2;
}
return dummyNode.next;
}
Complexity :
- Time: O(n)
- Space: O(1)
解釋
- 創建一個名為 dummyNode 的虛擬節點，當成合併後的 linked list 的頭。
- 創間一個變數 current，代表當下要追蹤的節點，初始化時先等於 dummyNode。
- 接著進入
while loop，只要兩個 list 都不是空的就會繼續執行。 - 在
while loop中比較 list1.val 和 list2.val
- 如果 list1.val 小於 list2.val，將 current 的 next 指针指向 list1，並將 list1 向後移動一個節點 ( list1 = list1.next )
- 如果 list2.val 小於 list1.val，將 current 的 next 指针指向 list2，並將 list2 向後移動一個節點 ( list2 = list2.next )
- 之後將 current 向後移動一個節點（current = current.next）
while loop結束後，可能其中一個 list 還有節點。檢查哪一個 list 還有節點，並將 current.next 指向剩餘的節點。- 最後回傳 dummyNode.next。虛擬節點後的下一個節點才是合併後的頭部。
解法 2:遞迴法
function (list1: ListNode | null, list2: ListNode | null): ListNode | null {
if (!list1) return list2;
if (!list2) return list1;
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
Complexity :
- Time: O(n)
- Space: O(n)