daily leetcode - merge-k-sorted-lists - !
题目地址
https://leetcode.com/problems/merge-k-sorted-lists/
题目描述
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
思路
这道题让我们合并k个有序链表,最终合并出来的结果也必须是有序的,之前做过一道 Merge Two Sorted Lists,是混合插入两个有序链表。这道题增加了难度,变成合并k个有序链表了,但是不管合并几个,基本还是要两两合并。那么首先考虑的方法是能不能利用之前那道题的解法来解答此题。答案是肯定的,但是需要修改,怎么修改呢,最先想到的就是两两合并,就是前两个先合并,合并好了再跟第三个,然后第四个直到第k个。这样的思路是对的,但是效率不高,没法通过 OJ,所以只能换一种思路,这里就需要用到分治法 Divide and Conquer Approach。简单来说就是不停的对半划分,比如k个链表先划分为合并两个 k/2 个链表的任务,再不停的往下划分,直到划分成只有一个或两个链表的任务,开始合并。举个例子来说比如合并6个链表,那么按照分治法,首先分别合并0和3,1和4,2和5。这样下一次只需合并3个链表,再合并1和3,最后和2合并就可以了。代码中的k是通过 (n+1)/2 计算的,这里为啥要加1呢,这是为了当n为奇数的时候,k能始终从后半段开始,比如当 n=5 时,那么此时 k=3,则0和3合并,1和4合并,最中间的2空出来。当n是偶数的时候,加1也不会有影响,比如当 n=4 时,此时 k=2,那么0和2合并,1和3合并,完美解决问题.
思路2
这道题目是合并 k 个已排序的链表,号称 leetcode 目前最难
的链表题。 和之前我们解决的88.merge-sorted-array很像。
他们有两点区别:
-
这道题的数据结构是链表,那道是数组。这个其实不复杂,毕竟都是线性的数据结构。
-
这道题需要合并 k 个元素,那道则只需要合并两个。这个是两题的关键差别,也是这道题难度为
hard
的原因。
因此我们可以看出,这道题目是88.merge-sorted-array
的进阶版本。其实思路也有点像,我们来具体分析下第二条。
如果你熟悉合并排序的话,你会发现它就是合并排序的一部分
。
具体我们可以来看一个动画
(动画来自 https://zhuanlan.zhihu.com/p/61796021 )
关键点解析
- 分治
- 合并排序(merge sort)
代码
解法一:
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL;
int n = lists.size();
while (n > 1) {
int k = (n + 1) / 2;
for (int i = 0; i < n / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[i + k]);
}
n = k;
}
return lists[0];
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
if (l2) cur->next = l2;
return dummy->next;
}
};
我们再来看另一种解法,这种解法利用了最小堆这种数据结构,首先把k个链表的首元素都加入最小堆中,它们会自动排好序。然后每次取出最小的那个元素加入最终结果的链表中,然后把取出元素的下一个元素再加入堆中,下次仍从堆中取出最小的元素做相同的操作,以此类推,直到堆中没有元素了,此时k个链表也合并为了一个链表,返回首节点即可,参见代码如下:
解法二:
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode*& a, ListNode*& b) {
return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp);
for (auto node : lists) {
if (node) q.push(node);
}
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (!q.empty()) {
auto t = q.top(); q.pop();
cur->next = t;
cur = cur->next;
if (cur->next) q.push(cur->next);
}
return dummy->next;
}
};
下面这种解法利用到了混合排序的思想,也属于分治法的一种,做法是将原链表分成两段,然后对每段调用递归函数,suppose 返回的 left 和 right 已经合并好了,然后再对 left 和 right 进行合并,合并的方法就使用之前那道 Merge Two Sorted Lists 中的任意一个解法即可,这里使用了递归的写法,而本题解法一中用的是迭代的写法,参见代码如下:
解法三:
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return helper(lists, 0, (int)lists.size() - 1);
}
ListNode* helper(vector<ListNode*>& lists, int start, int end) {
if (start > end) return NULL;
if (start == end) return lists[start];
int mid = start + (end - start) / 2;
ListNode *left = helper(lists, start, mid);
ListNode *right = helper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
下面这种解法利用到了计数排序的思想,由留言区二楼热心网友闽 A2436 提供,思路是将所有的结点值出现的最大值和最小值都记录下来,然后记录每个结点值出现的次数,这样从最小值遍历到最大值的时候,就会按顺序经过所有的结点值,根据其出现的次数,建立相对应个数的结点。但是这种解法有个特别需要注意的地方,那就是合并后的链表结点都是重新建立的,若在某些情况下,不能新建结点,而只能交换或者重新链接结点的话,那么此解法就不能使用,但好在本题并没有这种限制,可以完美过 OJ,参见代码如下:
解法四:
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
unordered_map<int, int> m;
int mx = INT_MIN, mn = INT_MAX;
for (auto node : lists) {
ListNode *t = node;
while (t) {
mx = max(mx, t->val);
mn = min(mn, t->val);
++m[t->val];
t = t->next;
}
}
for (int i = mn; i <= mx; ++i) {
if (!m.count(i)) continue;
for (int j = 0; j < m[i]; ++j) {
cur->next = new ListNode(i);
cur = cur->next;
}
}
return dummy->next;
}
};
代码2
代码支持 JavaScript, Python3
JavaScript Code:
/*
* @lc app=leetcode id=23 lang=javascript
*
* [23] Merge k Sorted Lists
*
* https://leetcode.com/problems/merge-k-sorted-lists/description/
*
*/
function mergeTwoLists(l1, l2) {
const dummyHead = {};
let current = dummyHead;
// l1: 1 -> 3 -> 5
// l2: 2 -> 4 -> 6
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
current.next = l1; // 把小的添加到结果链表
current = current.next; // 移动结果链表的指针
l1 = l1.next; // 移动小的那个链表的指针
} else {
current.next = l2;
current = current.next;
l2 = l2.next;
}
}
if (l1 === null) {
current.next = l2;
} else {
current.next = l1;
}
return dummyHead.next;
}
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// 图参考: https://zhuanlan.zhihu.com/p/61796021
if (lists.length === 0) return null;
if (lists.length === 1) return lists[0];
if (lists.length === 2) {
return mergeTwoLists(lists[0], lists[1]);
}
const mid = lists.length >> 1;
const l1 = [];
for (let i = 0; i < mid; i++) {
l1[i] = lists[i];
}
const l2 = [];
for (let i = mid, j = 0; i < lists.length; i++, j++) {
l2[j] = lists[i];
}
return mergeTwoLists(mergeKLists(l1), mergeKLists(l2));
};
Python3 Code:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
n = len(lists)
# basic cases
if lenth == 0: return None
if lenth == 1: return lists[0]
if lenth == 2: return self.mergeTwoLists(lists[0], lists[1])
# divide and conqure if not basic cases
mid = n // 2
return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
c1, c2, c3 = l1, l2, res
while c1 or c2:
if c1 and c2:
if c1.val < c2.val:
c3.next = ListNode(c1.val)
c1 = c1.next
else:
c3.next = ListNode(c2.val)
c2 = c2.next
c3 = c3.next
elif c1:
c3.next = c1
break
else:
c3.next = c2
break
return res.next
本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode