LeetCode: Merge k Sorted Lists

Description

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

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Naive solution

We can use a vector to collect all the nodes, and sort according to the values, then iterator the vector to construct a new LinkList.

Time complexity: $O(NlogN)$, where N is the number of all ListNode. Space complexity: $(N)$.

file:img/2020_01_29_merge-k-sorted-lists.org_20200129_203847.png

bool compare_node(ListNode* a, ListNode* b) {
    return a->val < b->val;
}

class Solution {
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    vector<ListNode*> vec;
    for(size_t i = 0; i < lists.size(); i++) {
      ListNode* p = lists[i];
      while(p) {
        vec.push_back(p);
        p = p->next;
      }
    }

    sort(vec.begin(), vec.end(), compare_node);

    ListNode res(0);
    ListNode* p = &res;
    for(size_t i = 0; i < vec.size(); i++) {
      vec[i]->next = NULL;
      p->next = vec[i];
      p = vec[i];
    }
    return res.next;
  }
};

Optimization with a priority queue

Another naive solution is also obvious, we can use K pointers to track the current pointer of each LinkList, iterate these pointers to find the minimum pointer in each round, extend the selected node to result.

Can we do better on time performance?

The answer is yes, we can use a priority queue to track the pointers. So that we don’t need to iterate K pointers in each round, instead we fetch the top node from the priority queue.

Time complexity: $O(NlogK) where N is the sum number of nodes, and K is the lists.size. This will be much better than the previous solution because K is smaller than N in most cases.

Space complexity: $O(N)$ and extra $(k)$ for priority queue.

file:img/2020_01_29_merge-k-sorted-lists.org_20200129_204819.png

struct cmp {
    bool operator() (ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};


class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        vector<ListNode*> vec = lists;
        ListNode res(0);
        ListNode* p = &res;
        priority_queue<ListNode*, vector<ListNode*>, cmp> Q;
        for(int i=0; i < lists.size(); i++) {
            if(lists[i] != NULL)
                Q.push(lists[i]);
        }
        while(!Q.empty()) {
            ListNode* t = Q.top();
            Q.pop();
            if(t->next)
                Q.push(t->next);
            t->next = NULL;
            p->next = t;
            p = t;
        }
        return res.next;
    }
};

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← LeetCode: Remove Duplicates from... Using Disjoint Set (Union-Find) ... →