## Friday, November 21, 2014

### [LeetCode] Merge k Sorted Lists

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

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25``` ```class Solution { public: struct compNode { bool operator()(ListNode *p, ListNode *q) const { return p->val>q->val; } }; ListNode *mergeKLists(vector &lists) { priority_queue, compNode> pq; ListNode *dummy = new ListNode(0), *tail = dummy; for(int i=0; inext = pq.top(); tail = tail->next; pq.pop(); if(tail->next) pq.push(tail->next); } return dummy->next; } }; ```

2n + 3n + ... + kn = [(k+1)*k/2-1]*n = O(nk^2)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26``` ```class Solution { public: ListNode *mergeKLists(vector &lists) { ListNode *ret = NULL; for(int i=0; ival<=h2->val) { tail->next = h1; h1 = h1->next; } else { tail->next = h2; h2 = h2->next; } tail = tail->next; } tail->next = h1 ? h1 : h2; return dummy->next; } }; ```

2n * k/2 + 4n * k/4 + ... + (2^x)n * k/(2^x) = nk * x
k/(2^x) = 1 -> 2^x = k -> x = log2(k)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33``` ```class Solution { public: ListNode *mergeKLists(vector &lists) { if(lists.empty()) return NULL; int end = lists.size()-1; while(end>0) { int begin = 0; while(beginval<=h2->val) { tail->next = h1; h1 = h1->next; } else { tail->next = h2; h2 = h2->next; } tail = tail->next; } tail->next = h1 ? h1 : h2; return dummy->next; } }; ```