LeetCode: Merge k Sorted Lists

自己写的太复杂了，一开始想的是给开始的lists头们排序，然后从这个序列的第一个抽出来，然后再重新用二分法进行排序，不过这个方法large超时了，看了网上的发现还是用很土地方法用一个for循环从前两个开始merge到最后，不知道为什么自己把这个想这么复杂。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *merge(ListNode *p, ListNode *q) {
12         if (!p) return q;
13         if (!q) return p;
14         ListNode *ret = NULL;
15         ListNode *reti;
16         while (p && q) {
17             if (!ret) {
18                 ret = new ListNode(min(p->val, q->val));
19                 reti = ret;
20                 if (p->val < q->val) p = p->next;
21                 else q = q->next;
22             }
23             else {
24                 ListNode *tmp = new ListNode(min(p->val, q->val));
25                 ret->next = tmp;
26                 ret = ret->next;
27                 if (p->val < q->val) p = p->next;
28                 else q = q->next;
29             }
30         }
31         if (!p) ret->next = q;
32         if (!q) ret->next = p;
33         return reti;
34     }
35     ListNode *mergeKLists(vector<ListNode *> &lists) {
36         // Start typing your C/C++ solution below
37         // DO NOT write int main() function
38         if (!lists.size()) return NULL;
39         ListNode *ret = lists[0];
40         for (int i = 1; i < lists.size(); i++) ret = merge(ret, lists[i]);
41         return ret;
42     }
43 };

推荐下面这个更符合面试的代码

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 struct cmp {
10     bool operator()(ListNode *a, ListNode *b) {
11         return a->val > b->val;
12     }
13 };
14 class Solution {
15 public:
16     ListNode *mergeKLists(vector<ListNode *> &lists) {
17         priority_queue<ListNode*, vector<ListNode*>, cmp> S;
18         if (lists.size() == 0) return NULL;
19         for (int i = 0; i < lists.size(); i++) {
20             if (lists[i]) S.push(lists[i]);
21         }
22         ListNode *ans = NULL;
23         ListNode *p = ans;
24         while (!S.empty()) {
25             ListNode *tmp = S.top();
26             if (!ans) {
27                 ans = tmp;
28                 p = ans;
29             }
30             else {
31                 p->next = tmp;
32                 p = p->next;
33             }
34             if (!tmp->next) S.pop();
35             else {
36                 tmp = tmp->next;
37                 S.pop();
38                 S.push(tmp);
39             }
40         }
41         return ans;
42     }
43 };