LC 23. Merge k Sorted Lists

Sarthak Sehgal · May 25, 2020

hard   linked list

Approach 1: Brute force [Accepted]

There can be several brute force approaches. Let’s consider the approaches and their time complexities:

Keep merging pair of lists

Merging two sorted lists together is simple. To merge k sorted lists, we just need to consider lists in pairs and keep merging them. If we have 3 lists, merge the first two lists and then merge the resulting list with the third list. Let’s analyze the time complexity of this approach. For simplicity, consider each list to be of fixed length “n” and assume that their are “k” such lists.

Merging two lists of size m and n takes O(m+n) time. So merging first two lists takes O(2n) time (let’s keep the constant 2 in the big-O notation for now as this is not the final time complexity). Now, the first two lists merge to make a list of length 2n. Now we have to merge this list with the third list. This takes time O(2n+n) = O(3n). So total time taken to merge 3 lists = O(2n+3n). Generalising this, total time to merge k lists would be O(2n+3n+4n+…+kn) = O(n*k*k). This doesn’t seem much efficient!

Keep finding the minimum

Another brute force approach could be to consider all the lists and find the minimum value. Then, only move the pointer of this list (where minimum value was found) to the next value and keep repeating this process. For example, if we have two lists 1->3 and 2->4, we will consider [1,2] in the first step. The minimum value is 1 so we will put it in the result and move the first pointer to the next value so we will consider [3,2] next and keep repeating the process.

Here, our array contains “k” elements each time we have to find the minimum. And we have to do this process n*k times as the total number of elements we have is n*k. So roughly the time complexity of this approach is O(n*k*k) as well.

Approach 2: Using min heap

Idea:

  1. Push all the pointers into a min heap (priority queue in C++) which compares them based on the value pointed. Use a min heap so that we get the minimum value each time we pop.
  2. While the heap contains a pointer, pop it and add it to the answer as it would be the next minimum element to be added. Further, push the next element in that list in the heap.
ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto comp = [](ListNode* a, ListNode* b) {return a->val>b->val;}; // lambda function to compare by value pointed
    priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);

    for(auto it : lists) {
        if (it!=NULL) pq.push(it);
    }

    ListNode* dummy = new ListNode(0);
    ListNode* prev = dummy;

    while (!pq.empty()) {
        ListNode* t = pq.top();
        pq.pop();
        if (t->next) pq.push(t->next);
        prev->next = new ListNode(t->val);
        prev = prev->next;
    }

    return dummy->next;
}

Time complexity: O(n*k*logk)
Space complexity: O(k)

Twitter, Facebook