Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Java:
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { // Start typing your Java solution below // DO NOT write main() function if(lists.size()==0) return null; PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){public int compare(ListNode a, ListNode b){return a.val>b.val?1:(a.val==b.val?0:-1);}}); for(ListNode list:lists){ if(list!=null) q.add(list); } ListNode head = new ListNode(0), prev = head; while(q.size()!=0){ ListNode temp = q.poll(); prev.next = temp; if(temp.next!=null) q.add(temp.next); prev = prev.next; } return head.next; } }
C++:
class CompareListNode { public: bool operator()(ListNode *n1, ListNode *n2) // Returns true if t1 is earlier than t2 { if (n1->val >= n2->val) return true; else return false; } }; class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. priority_queue<ListNode *, vector<ListNode *>, CompareListNode> q; for (const auto &list : lists) { if (list != NULL) { q.push(list); } } ListNode *output = NULL; ListNode *curr = output; while (q.size() > 0) { ListNode *temp = q.top(); if (curr == NULL) { output = temp; curr = output; } else { curr->next = temp; curr = curr->next; } q.pop(); if (temp->next != NULL) { q.push(temp->next); } } return output; } };
2 comments:
I think the most important for this problem is to analyze the time complexity. (1) for merging one by one consecutively, the time complexity is O(k ^ 2 * n); (2) for merging two lists at both ends at each time , it is O(k * n). How do you think ?
Post a Comment