Leetcode 23: Merge k Sorted Lists (O(kN) time)

leetcode_23a.cpp

#include <iostream>
#include <vector>

using namespace std;

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

ListNode* mergeKLists(vector<ListNode*>& lists) {
    int n = lists.size();
    if (n == 0) return NULL;
    ListNode dummy(0);
    dummy.next = lists[0];
    for (int i=1; i<n; ++i) {
        ListNode* prevNode = &dummy;
        ListNode* nodem = dummy.next; //merged list node
        ListNode* nodel = lists[i];
        while (nodem || nodel) {
            if (!nodel || (nodem && nodem->val < nodel->val)) {
                prevNode->next = nodem;
                nodem = nodem->next;
            }
            else {
                prevNode->next = nodel;
                nodel = nodel->next;
            }
            prevNode = prevNode->next;
        }
    }
    return dummy.next;
}

int main() {
    ListNode a1(1), a2(4), a3(5), b1(1), b2(3), b3(4), c1(2), c2(6);
    a1.next=&a2; a2.next=&a3; b1.next=&b2; b2.next=&b3; c1.next=&c2;
    vector<ListNode*> lists {&a1, &b1, &c1};
    auto node = mergeKLists(lists);
    while (node) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << "\n";
    return 0;
}