题目描述：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
因为之前做过Merge Two Sorted Lists，所以这道题也就显得不那么难了。
solution：
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; if(n == 1) return lists[0]; if(n == 2) return mergeTwoLists(lists[0], lists[1]); vector<ListNode *>::iterator mid = lists.begin() + n / 2; vector<ListNode *> front(lists.begin(), mid); vector<ListNode *> back(mid, lists.end()); return mergeTwoLists(mergeKLists(front), mergeKLists(back)); } ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if(l1 == NULL) return l2; if(l2 == NULL) return l1; ListNode *head = new ListNode(0); ListNode *p = head; while (l1 != NULL && l2 != NULL) { if (l1->val < l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } p->next = l1 ? l1 : l2; return head->next; }
参考链接：https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue
原文：http://www.cnblogs.com/gattaca/p/4360763.html