Merge k Sorted Lists [Leetcode]

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

Solutions: we first consider the problem of merging two sorted linked list, and then use it as a subroutine to merge  k sorted linked lists. Assume the size of sorted linked list l_i, 0 \le i \le n-1, is s_i, and there are n nodes in total. Now we have 3 choices:

1. Given a new linked list, say head,  without any node initially, we merge it with each sorted linked list in the vector<string> and the merge result is stored as head.  Each node in l_i is touched (i.e., compared) at most k-i times. Thus, the total number of comparison operations is s_0*k+s_1*(k-1)+...+s_{k-1}*1 \le nk, i..e, the time complexity is O(nk). The space complexity is constant.
2. In each round, we merge each pair of sorted linked lists l_i and l_{k-i},  0 \le i < k/2, in the vector<string>. At the end of round 1, the size of vector<string> is shrunk to k/2+k \mod 2. This process repeats until the size of vector<string> is shrunk to 1.  Each node is touched O(\log k) time, thus the time complexity is O(n \log k). The space complexity is constant.
3. Employ min_heap, please check here for more details. It is to be noted that Leecode OJ does not allow min_heap take function pointer as the third argument, which is weird. It is supposed to support both function pointer and fucntor...

   /*******************************SOLUTION 1***********************************/

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        ListNode* c1 = (l1->val<=l2->val?l1:l2); //pointing to the head with the smaller val
        ListNode* c2 = (l1->val<=l2->val?l2:l1); //pointing to the head with the larger val
        while(c1->next!=NULL && c2!=NULL){
            if(c1->val<=c2->val && c2->val<=c1->next->val){
                //insert c2 behind c1
                ListNode* tmp = c2->next;
                c2->next = c1->next;
                c1->next = c2;
                //advance both pointers
                c1 = c1->next;
                c2 = tmp;
            }
            else
                c1 = c1->next;
        }
        if(c1->next==NULL)
            c1->next = c2;
        return (l1->val<=l2->val?l1:l2);
    }
   
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        ListNode* head = NULL;
        for(int i=0; i<lists.size(); ++i){
            head = mergeTwoLists(head, lists[i]);
        }
        return head;
    }
};

  /*******************************SOLUTION 2**********************************/

 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        ListNode* c1 = (l1->val<=l2->val?l1:l2); //pointing to the head with the smaller val
        ListNode* c2 = (l1->val<=l2->val?l2:l1); //pointing to the head with the larger val
        while(c1->next!=NULL && c2!=NULL){
            if(c1->val<=c2->val && c2->val<=c1->next->val){
                //insert c2 behind c1
                ListNode* tmp = c2->next;
                c2->next = c1->next;
                c1->next = c2;
                //advance both pointers
                c1 = c1->next;
                c2 = tmp;
            }
            else
                c1 = c1->next;
        }
        if(c1->next==NULL)
            c1->next = c2;
        return (l1->val<=l2->val?l1:l2);
    }
   
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(lists.empty()) return NULL;
        while(lists.size()>1){
            int begin = 0, end =lists.size()-1;
            while(begin<end){
                lists[begin] = mergeTwoLists(lists[begin], lists[end]);
                lists.erase(lists.begin()+end);
                ++begin;
                --end;
            }
        }
        return lists[0];
    }
};