Merge k Sorted Lists

Question

参考 Merge Two Sorted Lists | Data Structure and Algorithm 中对两个有序链表的合并方法,这里我们也可以采用从 k 个链表中选择其中最小值的节点链接到lastNode->next(和选择排序思路有点类似),同时该节点所在的链表表头节点往后递推一个。直至lastNode遍历完 k 个链表的所有节点,此时表头节点均为NULL, 返回dummy->next.

这种方法非常简单直接,但是时间复杂度较高,容易出现 TLE.

C++

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
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/

class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.empty()) {
return NULL;
}

ListNode *dummy = new ListNode(INT_MAX);
ListNode *last = dummy;

while (true) {
int count = 0;
int index = -1, tempVal = INT_MAX;
for (int i = 0; i != lists.size(); ++i) {
if (NULL == lists[i]) {
++count;
if (count == lists.size()) {
last->next = NULL;
return dummy->next;
}
continue;
}

// choose the min value in non-NULL ListNode
if (NULL != lists[i] && lists[i]->val <= tempVal) {
tempVal = lists[i]->val;
index = i;
}
}

last->next = lists[index];
last = last->next;
lists[index] = lists[index]->next;
}
}
};

源码分析

  1. 由于头节点不定,我们使用dummy节点。
  2. 使用last表示每次归并后的新链表末尾节点。
  3. count用于累计链表表头节点为NULL的个数,若与 vector 大小相同则代表所有节点均已遍历完。
  4. tempVal用于保存每次比较 vector 中各链表表头节点中的最小值,index保存本轮选择归并过程中最小值对应的链表索引,用于循环结束前递推该链表表头节点。

复杂度分析

由于每次for循环只能选择出一个最小值,总的时间复杂度最坏情况下为 \[O(k \cdot \sum ^{k}_{i=1}l_i)\]. 空间复杂度近似为 \[O(1)\].

题解2 - 迭代调用Merge Two Sorted Lists(TLE)

鉴于题解1时间复杂度较高,题解2中我们可以反复利用时间复杂度相对较低的 Merge Two Sorted Lists | Data Structure and Algorithm. 即先合并链表1和2,接着将合并后的新链表再与链表3合并,如此反复直至 vector 内所有链表均已完全合并1

C++

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
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/

class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.empty()) {
return NULL;
}

ListNode *head = lists[0];
for (int i = 1; i != lists.size(); ++i) {
head = merge2Lists(head, lists[i]);
}

return head;
}

private:
ListNode *merge2Lists(ListNode *left, ListNode *right) {
ListNode *dummy = new ListNode(0);
ListNode *last = dummy;

while (NULL != left && NULL != right) {
if (left->val < right->val) {
last->next = left;
left = left->next;
} else {
last->next = right;
right = right->next;
}
last = last->next;
}

last->next = (NULL != left) ? left : right;

return dummy->next;
}
};

源码分析

实现合并两个链表的子方法后就没啥难度了,mergeKLists中左半部分链表初始化为lists[0], for循环后迭代归并headlists[i].

复杂度分析

合并两个链表时最差时间复杂度为 \[O(l_1+l_2)\], 那么在以上的实现中总的时间复杂度可近似认为是 \[l_1 + l_1+l_2 +...+l_1+l_2+...+l_k = O(\sum _{i=1} ^{k} (k-i) \cdot l_i)\]. 比起题解1复杂度是要小一点,但量级上仍然差不太多。实际运行时间也证明了这一点,题解2的运行时间差不多时题解1的一半。那么还有没有进一步降低时间复杂度的可能呢?当然是有的,且看下题分解...

题解3 - 二分调用Merge Two Sorted Lists

题解2中merge2Lists优化空间不大,那咱们就来看看mergeKLists中的for循环,仔细观察可得知第i个链表 \[l_i\] 被遍历了 \[k-i\] 次,如果我们使用二分法对其进行归并呢?从中间索引处进行二分归并后,每个链表参与合并的次数变为 \[\log k\], 故总的时间复杂度可降至 \[\log k \cdot \sum _{i=1} ^{k} l_i\]. 优化幅度较大。

C++

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
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/

class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.empty()) {
return NULL;
}

return helper(lists, 0, lists.size() - 1);
}

private:
ListNode *helper(vector<ListNode *> &lists, int start, int end) {
if (start == end) {
return lists[start];
} else if (start + 1 == end) {
return merge2Lists(lists[start], lists[end]);
}

ListNode *left = helper(lists, start, start + (end - start) / 2);
ListNode *right = helper(lists, start + (end - start) / 2 + 1, end);

return merge2Lists(left, right);
}

ListNode *merge2Lists(ListNode *left, ListNode *right) {
ListNode *dummy = new ListNode(0);
ListNode *last = dummy;

while (NULL != left && NULL != right) {
if (left->val < right->val) {
last->next = left;
left = left->next;
} else {
last->next = right;
right = right->next;
}
last = last->next;
}
last->next = (NULL != left) ? left : right;

return dummy->next;
}
};

源码分析

由于需要建立二分递归模型,另建一私有方法helper引入起止位置较为方便。下面着重分析helper

  1. 分两种边界条件处理,分别是start == endstart + 1 == end. 虽然第二种边界条件可以略去,但是加上会节省递归调用的栈空间。
  2. 使用分治思想理解helper, leftright的边界处理建议先分析几个简单例子,做到不重不漏。
  3. 注意merge2Lists中传入的参数,为lists[start]而不是start...

mergeKLists中调用helper时传入的end参数为lists.size() - 1,而不是lists.size().

复杂度分析

题解中已分析过,最坏的时间复杂度为 \[\log k \cdot \sum _{i=1} ^{k} l_i\], 空间复杂度近似为 \[O(1)\].

优化后的运行时间显著减少!由题解2中的500+ms 减至40ms 以内。

Reference


  1. soulmachine的LeetCode 题解↩︎


  


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×