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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| struct ListNode {
int val;
ListNode *next;
ListNode()
: val(0)
, next(nullptr)
{
}
ListNode(int x)
: val(x)
, next(nullptr)
{
}
ListNode(int x, ListNode *next)
: val(x)
, next(next)
{
}
};
#include <vector>
#include <queue>
using std::vector;
using std::queue;
class Solution {
private:
ListNode *merge2List(ListNode *l1, ListNode *l2)
{
ListNode dummy;
ListNode *tail = &dummy, *tmp;
while (l1 && l2) {
if (l1->val < l2->val) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
tail->next = tmp;
tail = tail->next;
}
tail->next = l1 == nullptr ? l2 : l1;
return dummy.next;
}
public:
ListNode *mergeKLists(vector<ListNode *> &lists)
{
int n = lists.size();
if (n == 0) {
return nullptr;
} else if (n == 1) {
return lists[0];
}
queue<ListNode *> que;
for (ListNode *&node : lists) {
que.push(node);
}
ListNode *l1, *l2;
while (que.size() != 1) {
l1 = que.front();
que.pop();
l2 = que.front();
que.pop();
que.push(merge2List(l1, l2));
}
return que.front();
}
};
|
wechat
alipay
