Image From LeetCodeImage From LeetCode

今天我們要講解的是 [Merge Two Sorted Lists]，這在 LeetCode 算是比較簡單的題目，讓我們一起開始吧！

進來之前請先注意，我的方式不一定完全正確，只是依照我自己的理念進行撰寫，所以如果程式上有什麼更好的解法，歡迎提出見解。

這次題目

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Example

1
2
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
1
2
Input: list1 = [], list2 = []
Output: []
1
2
Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

  • The number of nodes in list1 is in the range [0, 50].
  • -100 <= Node.val <= 100
  • list1 is sorted in non-decreasing order.

自已解法

這組題目跟上次解Add two number類似都是使用ListNode，不過這次是要進行排序，首先我們先建立題目要求的ListNode，

1
2
3
4
5
6
7
8
var mergeTwoLists = function(list1, list2) {

}

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
}

首先我們先判斷當各自的ListNode為空值時，讓他直接返還對方的ListNode，接著我們判斷list1的值是否小於list2，如果有的話，就針對list1去做遞迴，反之亦然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var mergeTwoLists = function(list1, list2) {
    if (!list1) {
        return list2;
    } else if (!list2) {
        return list1;
    } else if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
}

實作結果

這題目比較簡單，只要理解ListNode的原理就能快速地解出來，不過為了以為未來的我忘記，另外一種方法讓你瞭解ListNode是什麼鬼：

1
2
3
4
// list1 = [1, 2, 4]
const list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
// list2 = [1, 3, 4]
const list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
Image From LeetCodeImage From LeetCode