题目描述
合并 k 个排序链表
解决方案
我的解题思路是基于合并两个有序链表。合并k个链表时，若每次创建新的节点，可能需要较大内存，因此对上次的代码进行了改进，每次将现有的节点串起来，不再创建新节点。
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
| struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL)
return l2;
else if (l2 == NULL)
return l1;
ListNode *t1, *t2, *tmp;
int n = l1->val, m = l2->val;
if (n > m)
{
tmp = l1;
l1 = l2;
l2 = tmp;
}
t1 = l1;
t2 = l2;
while (t1&&t2)
{
ListNode *tmp1, *tmp2;
n = t1->val, m = t2->val;
if (n > m)
while (t2->next&&t2->next->val <= n)
t2 = t2->next;
else if(n<m)
while (t1->next&&t1->next->val <= m)
t1 = t1->next;
tmp1 = t1->next;
t1->next = t2;
t1 = t2;
tmp2 = t2->next;
if (t1 != NULL)
t2->next = tmp1;
else
return l1;
t2 = tmp2;
}
if (t2)
t1 = t2;
return l1;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int num = lists.size();
if (num == 0)
return NULL;
else if (num == 1)
return lists[0];
ListNode* res = lists[0];
for (size_t i = 1; i < num; i++) {
res = mergeTwoLists(res, lists[i]);
}
return res;
}
|