Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
--------------------------------------------------------------
Solution #1 O(k*n)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *merge2Lists (ListNode *l1, ListNode *l2) {
ListNode *ret,*cur;
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val < l2->val) {
ret = l1;
cur = l1;
l1 = l1->next;
}else {
ret = l2;
cur = l2;
l2 = l2->next;
}
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
cur->next = l1;
cur = cur->next;
l1 = l1->next;
}else {
cur->next = l2;
cur = cur->next;
l2 = l2->next;
}
}
if (l1 == NULL) {
cur->next = l2;
}else {
cur->next = l1;
}
return ret;
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (lists.size() == 0) return NULL;
ListNode *ret = lists[0];
for (int i=1;i<lists.size();i++) {
ret = merge2Lists(ret,lists[i]);
}
return ret;
}
};
Solution #2, O（nlogk）, using Priority Queue
note struct of comparison function and declaration of priority queue
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct comp{
bool operator()(const ListNode* n1, const ListNode* n2){
return n1->val > n2->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
priority_queue<ListNode*,vector<ListNode*>,comp> heap;
ListNode *ret=NULL,*cur;
for (int i=0;i<lists.size();i++) {
if (lists[i] != NULL) {
heap.push(lists[i]);
}
}
while (!heap.empty()) {
ListNode *min = heap.top();
heap.pop();
if (ret == NULL) {
ret = min;
cur = min;
}else {
cur->next = min;
cur = cur->next;
}
if (min->next != NULL) {
heap.push(min->next);
}
}
return ret;
}
};
Update on Sep-11-2014 Solution #3, push all nodes in priority_queue, then output will be in order
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct cmp {
bool operator()(const ListNode* l1, const ListNode* l2) {
return l1->val > l2->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
ListNode *dummy = new ListNode(INT_MIN);
priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
bool flag = true;
while (flag) {
flag = false;
for (int i = 0; i < lists.size(); i++) {
if (lists[i] != NULL) {
flag = true;
heap.push(lists[i]);
lists[i] = lists[i]->next;
}
}
}
ListNode *head = dummy;
while (!heap.empty()) {
ListNode *t = heap.top();
head->next = t;
heap.pop();
head = t;
}
head->next = NULL; // prevent infinite loop
return dummy->next;
}
};
Solution #4, merge all pairs of two adjacent lists for each iteration. O(nlog(k)), n is the total elements from all listsUpdate on Nov-26-2014
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *merge2Lists (ListNode *l1, ListNode *l2) {
ListNode *ret,*cur;
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val < l2->val) {
ret = l1;
cur = l1;
l1 = l1->next;
}else {
ret = l2;
cur = l2;
l2 = l2->next;
}
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
cur->next = l1;
cur = cur->next;
l1 = l1->next;
}else {
cur->next = l2;
cur = cur->next;
l2 = l2->next;
}
}
if (l1 == NULL) {
cur->next = l2;
}else {
cur->next = l1;
}
return ret;
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (lists.size() == 0) return NULL;
int size = lists.size();
while (size != 1) {
for (int i = 0; i < size; i = i + 2) {
if (i + 1 < size) {
lists[i / 2] = merge2Lists(lists[i],lists[i + 1]);
}else{
lists[i / 2] = lists[i];
}
}
size = size / 2 + size % 2;
}
return lists[0];
}
};
与上面同样思路，但是用递归
/**
* 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) {
ListNode *dummy = new ListNode(0), *itr = dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val > l2->val) {
itr->next = l2;
l2 = l2->next;
itr = itr->next;
}else {
itr->next = l1;
l1 = l1->next;
itr = itr->next;
}
}
if (l1 == NULL) {
itr->next = l2;
}
if (l2 == NULL) {
itr->next = l1;
}
return dummy->next;
}
ListNode* helper(vector<ListNode*> &lists,int start,int end) {
if (start > end) return NULL;
if (start == end) return lists[start];
int mid = (start + end) / 2;
ListNode *l1 = helper(lists,start,mid);
ListNode *l2 = helper(lists,mid + 1,end);
return mergeTwoLists(l1,l2);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return helper(lists,0,lists.size() - 1);
}
};
Java, 用priority queue时间O(N * log k), 空间为O(k), N为总node的个数，k为list的数量。
先把所有的头指针插入到queue，然后一个个pop。把刚pop出来的node的一下个，推回queue
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue que = new PriorityQueue<>((a, b) -> {
return a.val - b.val;
});
for (ListNode node : lists) {
if (node != null) que.add(node);
}
ListNode dummy = new ListNode(0);
ListNode itr = dummy;
while (!que.isEmpty()) {
ListNode next = que.poll();
if (next.next != null) que.add(next.next);
itr.next = next;
itr = next;
}
return dummy.next;
}
}
如果可以重复利用原来的array的话，空间可以算是O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
List rt = Arrays.asList(lists);
while (rt.size() != 1) {
rt = divide(rt);
}
return rt.get(0);
}
private List divide(List lists) {
int n = lists.size();
List rt = new ArrayList<>();
for (int i = 0; i < n / 2; i++) {
rt.add(mergeTwo(lists.get(i), lists.get(n - 1 - i)));
}
if (n % 2 == 1) rt.add(lists.get(n / 2));
return rt;
}
private ListNode mergeTwo(ListNode node1, ListNode node2) {
if (node1 == null) return node2;
if (node2 == null) return node1;
ListNode dummy = new ListNode(0);
ListNode itr;
if (node1.val > node2.val) {
dummy.next = node2;
node2 = node2.next;
}else {
dummy.next = node1;
node1 = node1.next;
}
itr = dummy.next;
while (node1 != null && node2 != null) {
if (node1.val > node2.val) {
itr.next = node2;
itr = node2;
node2 = node2.next;
}else {
itr.next = node1;
itr = node1;
node1 = node1.next;
}
}
if (node1 != null) {
itr.next = node1;
}
if (node2 != null) {
itr.next = node2;
}
return dummy.next;
}
}
