Skip to content

Instantly share code, notes, and snippets.

@adamkorg
Created December 28, 2019 23:46
Show Gist options
  • Save adamkorg/665adeec343a9a114e1088833f96dbb8 to your computer and use it in GitHub Desktop.
Save adamkorg/665adeec343a9a114e1088833f96dbb8 to your computer and use it in GitHub Desktop.
Leetcode 23: Merge k Sorted Lists (O(kN) time)
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment