# 21. Merge Two Sorted Lists

### Leetcode

<https://leetcode.com/problems/merge-two-sorted-lists/>

### 題目

You are given the heads of two sorted linked lists `list1` and `list2`.

Merge the two lists in a 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*.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg)

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

**Example 2:**

```
Input: list1 = [], list2 = []
Output: []
```

**Example 3:**

```
Input: list1 = [], list2 = [0]
Output: [0]
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

```
var mergeTwoLists = function(list1, list2) {
    if(!list1) return list2;
    if(!list2) return list1;
    
    let head = list1.val <= list2.val ? list1 : list2;
        
    let p1 = head.next;
    let p2 = head === list1 ? list2 : list1;
    
    const result = head;
    
    while(p1 && p2) {
        if(p1.val<=p2.val) {
            head.next = p1;
            head = p1;
            p1 = p1.next;
        } else {
            head.next = p2;
            head = p2;
            p2 = p2.next;
        }
    }
    // 其中一個 pointer 為 null 的話，剩下的要指向另一個 linked list
    if(!p1) head.next = p2;
    if(!p2) head.next = p1;
    
    return result;
};
```

Runtime: 113 ms, faster than 39.65% of JavaScript online submissions for Merge Two Sorted Lists.

Memory Usage: 44.3 MB, less than 5.02% of JavaScript online submissions for Merge Two Sorted Lists.

* **方法二**

Recursion

```
var mergeTwoLists = function(list1, list2) {
    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;
    }
};
```

Runtime: 145 ms, faster than 14.29% of JavaScript online submissions for Merge Two Sorted Lists.

Memory Usage: 43.9 MB, less than 6.58% of JavaScript online submissions for Merge Two Sorted Lists.

* **方法三**

創建一個 dummy node 改良方法一

```
var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode(-1);
    
    let head = dummy;
    while(list1 && list2) {
        if(list1.val <= list2.val) {
            head.next = list1;
            list1 = list1.next;
        } else {
            head.next = list2;
            list2 = list2.next;
        }
        head = head.next;
    }
    
    head.next = list1 === null ? list2 : list1;
    return dummy.next;
};
```

Runtime: 117 ms, faster than 37.19% of JavaScript online submissions for Merge Two Sorted Lists.

Memory Usage: 44 MB, less than 5.97% of JavaScript online submissions for Merge Two Sorted Lists.

Time complexity : O(n+m)

Space complexity : O(1)
