all articles

leetcode war 23 - Merge k Sorted Lists

2017-10-22 @sunderls

leetCode js

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

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

analysis

we've done a k=2 case at our last article - leetcode war 21 - Merge Two Sorted Lists, it cost a O(m * 2) because each comparison of the heads of the lists generate a node in the final list.

so for k sorted list, if we do it in a same fasion, it would cost us O(m * k) * k, right? Every round we get the smallest number from k heads, which is O(k), and there art m k rounds, so O(m k2).

is there a better way ? comparing k elements every time seems very not performant. what if we do it in groups of two ? and merge them seperately?

  1. 1st round: k/2 groups, each cost O(m * 2), O(m * 2 * k / 2) = O(m * k)
  2. 2nd round: k/4 groups, each cost O(2m * 2), O(m * 4 * k / 4) = O(m * k)
  3. ..
  4. lg(k) round

so we can do it better with O(m * k * lg(k)) complexity.

trial

we put in our solution method mergeTwoLists, and use a while loop to do this.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
var mergeTwoLists = function(l1, l2) {
    var p1 = l1;
    var p2 = l2;
    var head = p3 = new ListNode();

    while (p1 && p2) {
        if (p1.val <= p2.val) {
            p3.next = p1;
            p1 = p1.next;
        } else {
            p3.next = p2;
            p2 = p2.next;
        }

        p3 = p3.next;
    }

    if (p1) {
        p3.next = p1;
    }

    if (p2) {
        p3.next = p2;
    }

    return head.next;
};

var mergeKLists = function(lists) {
    if (lists.length === 0) return null;
    // if there are more than one list
    // shift them out, merge them, and push them back
    while(lists.length > 1) {
        var a = lists.shift();
        var b = lists.shift();
        lists.push(mergeTwoLists(a, b));
    }
    return lists[0];
};

it passed! and ranking top 10% fast submissions, 168 ms. wow.

can we do better?

what if we do it one by one, rather than in groups, like

  1. 1st round: O(m * 2), now k - 1 lists left
  2. 2nd round: O(m * 3), now k - 2 lists left
  3. .. n. nth round: O(m * (n + 1)), now k - n lists left k. (k - 1)th round: O(m * k)), now 1 lists left

so complexity is: m * 2 + m * 3 + m * k = m * k(k + 1)/ 2 = O(m * k * k)

not better than our grouping method.

while there is a solution page on leetcode, and our method is the fastest way, called Divide And Conquer .

sorry I've already forgot after graduation.