Merge k Sorted Lists Solutions in C++

// Source : https://oj.leetcode.com/problems/merge-k-sorted-lists/
// Author : Hao Chen
// Date   : 2014-07-06



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *mergeTwoLists(ListNode* head1, ListNode* head2);
ListNode *mergeTwoLists01(ListNode* head1, ListNode* head2);
ListNode *mergeTwoLists02(ListNode* head1, ListNode* head2);

ListNode *mergeKLists(vector<ListNode *> &lists) {
    ListNode *p, *p1, *p2;
    while(lists.size()>1){
        p1 = lists.back();    
        lists.pop_back();
        p2 = lists.back();    
        lists.pop_back();
        p = mergeTwoLists(p1, p2);
        lists.insert(lists.begin(), p);
    }
    return lists.size()==1 ? lists[0] : NULL;

    /* the following method is not fast enough! */
    /*
    ListNode* pHead = NULL;
    for (int i=0; i<lists.size(); i++){
        pHead = mergeTwoLists(pHead, lists[i]);
    }
    return pHead;
    */
}

static int n=0;
ListNode *mergeTwoLists(ListNode* head1, ListNode* head2){
    if (n){
        //cout << "------ method 01 ------" <<endl;
        return mergeTwoLists01(head1, head2);
    }
    //cout << "------ method 02 ------" <<endl;
    return mergeTwoLists02(head1, head2);
}
/*======================================================================*/
/*                            Method One                                */
/*======================================================================*/

//#define INT_MAX   2147483647
//#define INT_MIN   (-INT_MAX - 1)

ListNode *mergeTwoLists01(ListNode* head1, ListNode* head2){
    ListNode *p1 = head1,  *p2=head2;
    static ListNode dummy(0);

    dummy.next = p1;
    ListNode *prev = &dummy;

    while(p1 && p2){
        if(p1->val < p2->val){
            prev = p1;
            p1 = p1->next;
        }else{
            prev->next = p2;
            p2 = p2->next;
            prev = prev->next;
            prev->next = p1;
        }
    }
    if (p2){
        prev->next = p2;
    }

    return dummy.next;
}

/*======================================================================*/
/*                            Method Two                                */
/*======================================================================*/


void TakeOutNode(ListNode*& head, ListNode*& tail, ListNode*& p);

ListNode *mergeTwoLists02(ListNode* head1, ListNode* head2) {
    ListNode *p1 = head1,  *p2=head2;

    ListNode *pHead = NULL, *pTail=NULL;
    while(p1 && p2){
        if(p1->val < p2->val){
            TakeOutNode(pHead, pTail, p1);
        }else{
            TakeOutNode(pHead, pTail, p2);
        }
    }

    ListNode *p=NULL;
    if (p1){
        p = p1;
    }else if (p2){
        p = p2;
    }
    if (pHead==NULL){
        return p;
    }
    pTail->next = p;
    return pHead;
}

void TakeOutNode(ListNode*& head, ListNode*& tail, ListNode*& p){
    ListNode *pNext = p->next;
    if (head==NULL){
        head = tail = p;
    }else{
        tail->next = p;
        tail = p;
    }
    p->next = NULL;
    p = pNext;
}

void printList(ListNode* h)
{
    while(h!=NULL){
        printf("%d ", h->val);
        h = h->next;
    }
    printf("\n");
}

ListNode* createList(int a[], int n)
{
    ListNode *head=NULL, *p=NULL;
    for(int i=0; i<n; i++){
        if (head == NULL){
            head = p = new ListNode(a[i]);
        }else{
            p->next = new ListNode(a[i]);
            p = p->next;
        }
    }
    return head;
}


int main(int argc, char**argv)
{
    srand(time(0));
    if (argc>1){
        n = atoi(argv[1]) % 2;
    }

    int a[] = {1,3,5,6,7,10};
    int b[] = {0,4,6,8,9,11,20,30,40};
    ListNode* p1 = createList(a, sizeof(a)/sizeof(int));
    ListNode* p2 = createList(b, sizeof(b)/sizeof(int));

    printList( mergeTwoLists(p1,p2) );
    //mergeTwoLists(p1,p2) ;


    vector<ListNode*> v;
    for(int i=0; i<10240; i++) {
        v.push_back(new ListNode(random()%100));
    }
    printList( mergeKLists(v) );
    //mergeKLists(v);


    cout << "method " << n+1 << endl;
    return 0;
}

#include <vector>
using std::vector;
#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = NULL, **lastPtrRef = &head;
        for (;l1 && l2; lastPtrRef = &((*lastPtrRef)->next)) {
            if (l1->val <= l2->val) { *lastPtrRef = l1; l1 = l1->next; }
            else { *lastPtrRef = l2; l2 = l2->next; }
        }
        *lastPtrRef = l1 ? l1 : l2;
        return head;
    }

    using vecNodeCIter = vector<ListNode *>::const_iterator;
    ListNode *mergeKLists(vecNodeCIter beg, vecNodeCIter end) {
        if (beg == end) return NULL;
        else if (std::distance(beg, end) == 1) return *beg;
        else if (std::distance(beg, end) == 2) return mergeTwoLists(*beg, *std::next(beg));
        else return mergeTwoLists(mergeKLists(beg, beg + std::distance(beg, end)/2), mergeKLists(beg + std::distance(beg, end)/2, end));
    }
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return mergeKLists(lists.cbegin(), lists.cend());
    }
};

/// Source : https://leetcode.com/problems/merge-k-sorted-lists/description/
/// Author : liuyubobobo
/// Time   : 2018-07-02

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/// Linear Compare each ListNode
/// Time Complexity: O(k*n) where k is len(lists) and n is the nodes number
/// Space Complexity: O(1)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        if(lists.size() == 0)
            return NULL;

        ListNode* dummyHead = new ListNode(-1);
        ListNode* curNode = dummyHead;

        int finished = 0;
        for(ListNode* node: lists)
            if(node == NULL)
                finished ++;

        while(finished < lists.size()){

            ListNode* nextNode = NULL;
            int nextIndex = -1;
            for(int i = 0 ; i < lists.size() ; i ++)
                if(lists[i] != NULL){
                    if(nextIndex == -1 || lists[i]->val < nextNode->val){
                        nextNode = lists[i];
                        nextIndex = i;
                    }
                }
            assert(nextIndex != -1 && nextNode != NULL);

            lists[nextIndex] = lists[nextIndex]->next;
            if(lists[nextIndex] == NULL)
                finished ++;

            curNode->next = nextNode;
            nextNode->next = NULL;
            curNode = curNode->next;
        }

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/merge-k-sorted-lists/description/
/// Author : liuyubobobo
/// Time   : 2018-07-02

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class CompareListNode{
public:
    bool operator()(ListNode* node1, ListNode* node2){
        return node1->val > node2->val;
    }
};

/// Using Priority Queue to compare each ListNode
/// Time Complexity: O(nlogk) where k is len(lists) and n is the nodes number
/// Space Complexity: O(1)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        if(lists.size() == 0)
            return NULL;

        ListNode* dummyHead = new ListNode(-1);
        ListNode* curNode = dummyHead;

        priority_queue<ListNode*, vector<ListNode*>, CompareListNode> q;
        for(ListNode* node: lists)
            if(node != NULL)
                q.push(node);

        while(!q.empty()){

            ListNode* nextNode = q.top();
            q.pop();


            curNode->next = nextNode;
            if(nextNode->next != NULL)
                q.push(nextNode->next);

            nextNode->next = NULL;
            curNode = curNode->next;
        }

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/merge-k-sorted-lists/description/
/// Author : liuyubobobo
/// Time   : 2018-07-02

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/// Merge List One by One
/// Time Complexity: O(k*n), where k is len(lists) and n is the nodes number
/// Space Complexity: O(1)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        if(lists.size() == 0)
            return NULL;

        ListNode* ret = NULL;
        for(ListNode* list: lists)
            ret = merge(ret, list);
        return ret;
    }

private:
    ListNode* merge(ListNode* list1, ListNode* list2){

        ListNode* dummyHead = new ListNode(-1);
        ListNode* curNode = dummyHead;
        while(list1 != NULL && list2 != NULL){
            if(list1->val < list2->val){
                curNode->next = list1;
                list1 = list1->next;
            }
            else{
                curNode->next = list2;
                list2 = list2->next;
            }

            curNode = curNode->next;
            curNode->next = NULL;
        }

        if(list1)
            curNode->next = list1;
        if(list2)
            curNode->next = list2;

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/merge-k-sorted-lists/description/
/// Author : liuyubobobo
/// Time   : 2018-07-02

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>

using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/// Merge List with Divide and Conquer
/// Using the Bottom-Up Merge
/// Since Top-Down Merge will lead to TLE :-(
///
/// Time Complexity: O(nlogk), where k is len(lists) and n is the nodes number
/// Space Complexity: O(logk)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        if(lists.size() == 0)
            return NULL;

        while(lists.size() > 1){
            int index = 0;
            for(int i = 0; i < lists.size() ; i += 2){
                if(i + 1 == lists.size())
                    lists[index] = lists[i];
                else
                    lists[index] = merge(lists[i], lists[i + 1]);
                index ++;
            }

            while(lists.size() > index)
                lists.pop_back();
        }
        return lists[0];
    }

private:
    ListNode* merge(ListNode* list1, ListNode* list2){

        ListNode* dummyHead = new ListNode(-1);
        ListNode* curNode = dummyHead;
        while(list1 != NULL && list2 != NULL){
            if(list1->val < list2->val){
                curNode->next = list1;
                list1 = list1->next;
            }
            else{
                curNode->next = list2;
                list2 = list2->next;
            }

            curNode = curNode->next;
            curNode->next = NULL;
        }

        if(list1)
            curNode->next = list1;
        if(list2)
            curNode->next = list2;

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};


int main() {

    return 0;
}