链接:
https://leetcode-cn.com/problems/merge-k-sorted-lists
描述:
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
ListNode* mergeKLists(vector<ListNode*>& lists) {}
简单题
【LeetCode】21. 合并两个有序链表
https://www.cnblogs.com/crazyBlogs/p/13164038.html
思路:逐一合并
用变量 (result) 表示已经合并的链表,
循环遍历所有链表,将当前链表和 (result) 合并。
C++
展开后查看
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* result = NULL;
for(ListNode* list: lists){
result = merge2Lists(result, list);
}
return result;
}
};
Java
展开后查看
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode result = null;
for(ListNode list: lists){
result = merge2Lists(result, list);
}
return result;
}
}
思路:分治合并
用分治法进行合并
C++
展开后查看
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0){
return NULL;
}
return merge(lists, 0, lists.size() - 1);
}
ListNode* merge(vector<ListNode*>&lists, int left, int right){
if(left == right){
return lists[left];
}
int mid = left + (right - left) / 2;
ListNode* list1 = merge(lists, left, mid);
ListNode* list2 = merge(lists, mid + 1, right);
return merge2Lists(list1, list2);
}
}
Java
展开后查看
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0){
return null;
}
return merge(lists, 0, lists.length - 1);
}
ListNode merge(ListNode[] lists, int left, int right){
if(left == right){
return lists[left];
}
int mid = left + (right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return merge2Lists(l1, l2);
}
}