[LeetCode HARD] 23 Merge k Sorted Lists

LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode “hard”, “medium”, and “easy” problems are more like “easy”, “very easy”, “extremely easy” for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. Hope it would be helpful for people who are preparing for tech interviews.

This is my 3rd LeetCode solution article, for LeetCode Problem 23, Merge k Sorted Lists.

Problem

Given k sorted singly linked lists, combine them to one sorted singly linked list.

Solution

We construct the result linked list as follow: we pick the smallest element, then delete the element from the linked list it is from. Then pick the smallest from the remaining items, and so on.

The smallest item would be the smallest of all linked lists’ first items. To find it in O(log(n)) time, we need to have some type of O(log(n)) priority queue.

Source Code

In C++, using std::set for priority queue.

 
/** * /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head, *tail;
        head = tail = new ListNode(0);
        
        std::set<std::pair<int, unsigned int> > pq;
        for (unsigned int i =0; i < lists.size(); ++i) 
            addElement(pq, lists, i);
        
        while (!pq.empty()) {
            auto b = *pq.begin();
            pq.erase(pq.begin());
            
            ListNode *newNode = new ListNode(b.first);
            tail->next = newNode;
            tail = newNode;
            
            addElement(pq, lists, b.second);
        }
        auto ret = head->next;
        delete head;
        return ret;
    }
    
private:
    void addElement(std::set<std::pair<int, unsigned int> > &pq, vector<ListNode*>& lists, unsigned int i) {
        if (lists[i] != nullptr) {
            pq.insert(std::make_pair(lists[i]->val, i) );
            lists[i] = lists[i]->next;
        }
    }
};