Time Cost

14min45s

Implementation

My initial solution is soltion 1 which passed in first attempt with bad runtime (beats 6.81%). Solution 1 is very intuitive which we maintain a vector to represent nodes in each linkedlist and moves forward if current node is the smallest compared to other nodes in linkedlist.

In Solution 2, we directly use min heap to get the smallest node at the moment. Just make sure build right struct compare and use it in priority_queue.

Code

• Solution 1

  class Solution {
  public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // have many linkedlist
        // give each linkedlist independent pointer;
        // - compare each value in different linkedlist
        // - choose the smallest value and move forward the pointer on that linkedlist
  
        ListNode* head = new ListNode;
        ListNode* prev = head;
  
        vector<ListNode*> current = lists;
  
        while (true) {
            int min_value = INT_MAX, index = -1;
            ListNode* chosed;
            for (int i=0; i<current.size(); i++) {
                if (current[i] != nullptr && min_value > current[i]->val) {
                    chosed = current[i];
                    index = i;
                    min_value = current[i]->val;
                }
            }
            if (index == -1) break;
            current[index] = current[index]->next;
            prev->next = chosed;
            prev = chosed;
        }
  
        return head->next;
    }
  };
  

• Solution 2

  class Solution {
  public:
    struct compare {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };
      
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, compare> pq;
        for (auto l : lists) {
            if (l) pq.push(l);
        }
          
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
          
        while (!pq.empty()) {
            ListNode* curr = pq.top();
            pq.pop();
            tail->next = curr;
            tail = tail->next;
            if (curr->next) pq.push(curr->next);
        }
        return dummy->next;
    }
  };