23. Merge k Sorted Lists

Leetcode

https://leetcode.com/problems/merge-k-sorted-lists/

題目

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

解答

• 方法一

仿照 21. 題 方法三的解法，所有的 lists 在同一輪先找出最小值

var mergeKLists = function(lists) {
    const prevNode = new ListNode(-1);
    let head = prevNode;
    
    while(lists.filter(Boolean).length >= 2) {
        // list 為 null 時，設成最大數字
        const values = lists.map(list => list?.val ?? Number.MAX_SAFE_INTEGER);
        const min = values.indexOf(Math.min(...values));
        head.next = lists[min];
        lists[min] = lists[min].next;
        head = head.next;
    }
    
    const last = lists.find(list => list);
    if(last) head.next = last;
    
    return prevNode.next;
};

Runtime: 4802 ms, faster than 5.01% of JavaScript online submissions for Merge k Sorted Lists.

Memory Usage: 74.4 MB, less than 5.00% of JavaScript online submissions for Merge k Sorted Lists.

Time complexity : O(kN) where k is the number of linked lists.

每次比較最小值都是 k 次，總共有 N 個 node 要比較

Space complexity : O(1)

• 方法二

將 lists 兩兩 套用 21. 題 方法三的解法，接著最後 merge 在一起

ex. [list1, list2, list3, list4] => [list12, list34] => [list1234]

var mergeKLists = function(lists) {
    // From Question 21. Answer 3
    var mergeTwoLists = function(list1, list2) {
        const prevNode = new ListNode(-1);

        let head = prevNode;
        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 prevNode.next;
    };
    
    while(lists.length > 1) {
        const newLists = [];
        // merge two lists
        for(let i=0; i<lists.length; i+=2) {
            const mergeList = mergeTwoLists(lists[i], lists[i+1]);
            newLists.push(mergeList);
        }
        lists = newLists;
    }
    
    // For the edge case of [], undefined -> null
    return lists[0] ?? null;
};

Runtime: 144 ms, faster than 63.26% of JavaScript online submissions for Merge k Sorted Lists.

Memory Usage: 47.3 MB, less than 15.01% of JavaScript online submissions for Merge k Sorted Lists.

Time complexity : O(Nlogk) where k is the number of linked lists.

Space complexity : O(1)