Merge Sorted Array

Merge

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

Analysis:

While the lists is not empty, keep merging the list to the result list. Method to merge two lists is the same as Question 54

Code(updated 201309):

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { // Start typing your C/C++ solution below // DO NOT write int main() function ListNode* head=new ListNode(0); if (lists.size()==0){return NULL;} head->next = lists[0]; ListNode *p; ListNode *q; for (int i=1;i<lists.size();i++){ p = head; q = lists[i]; while (q){ if (!p->next){ p->next = q; break; } if (p->next->val<q->val){ p=p->next; }else{ ListNode *l = p->next; p->next = q; q=q->next; p->next->next = l; p=p->next; } } } return head->next; } };

Code(old version):

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* merg2(ListNode* l1, ListNode* l2){ ListNode* head = new ListNode(0); head->next = l1; ListNode* prev = head; if (l1==NULL){ head->next=l2; } while (l1!=NULL && l2!=NULL){ if (l1->val < l2->val){ if (l1->next != NULL){ prev = l1; l1=l1->next; }else{ l1->next = l2; break; } }else{ ListNode* tmp = l2->next; prev->next = l2; l2->next = l1; prev = l2; l2 = tmp; } } return head->next; } ListNode *mergeKLists(vector<ListNode *> &lists) { // Start typing your C/C++ solution below // DO NOT write int main() function if (lists.empty()){return NULL;} ListNode *head = lists.back(); lists.pop_back(); while (!lists.empty()){ head = merg2(head,lists.back()); lists.pop_back(); } return head; }

if merge one by one, that'll be O(k^2 * n), assuming they n is the average length of the lists. try merge sort(for lists) of merge sort(for two lists), i.e. divide and conquer. running time reduced to O(logk*k*n).

ReplyDeleteHi Nison, I understand that the number of comparison is in the order of O(n * k ^ 2) if merging one by one. But the number of comparison of merging two lists at both ends at each time is in the order of O(k * n ), that is what I got from calculation. How did you get O(n * k * logk)?

DeleteMaybe use a priority queue to store all the nodes instead of arraylist?

DeleteExcuse for my little ads.

ReplyDeleteGood solution in O(n*n*m). Find out the O((n*m)*log(m)) here

http://fmarss.blogspot.com/2014/09/leetcode-solution_11.html

Get time limit exceeded with your code in OJ.

ReplyDelete