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.

Example 1:

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]

解答

• 方法一

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)