k个链表归并(Leetcode23)
2018-11-07 本文已影响0人
zhouwaiqiang
题目要求
在21题的基础上，增长到k个有序链表，给定一个链表数组，将其归并，并分析其时间复杂度和空间复杂度。
解题思路
- 无论多少个链表的归并都是由2个链表慢慢归并得来，因此最基础的还是题21中的两个链表归并，基础算法
- 对于k个链表可以采用最蠢的方式就是挨个遍历，选择起始两个得到一个结果后，再与后面的数据挨个合并，但是这样会造成时间复杂度的增大，其次数组下标递增时得到的都是所有之前链表的总和，空间复杂度也在不断增大，当这个数组中的每个链表都是较大的数据量时，很容易出现超内存崩溃的情况。（死过不知道多少次了）
- 目前我采取的办法是2-2合并的方式，举例来说一个数组有10个链表，其length长度为10，那么既然我最后要归并得到一个链表，我可以采用每2个数据合并的方式加快合并，设定一个起始的两两合并下标值k=1，也就是下标0,1合并然后覆盖到下标0,下标2,3合并覆盖下标2,下标4,5合并覆盖下标4，依次类推。然后再进行第二轮循环k=2,下标0,2合并覆盖下标0,下标4,6合并覆盖下标4，再依次类推。第三轮k=4，一直重复上面的动作直到k的值大于数组长度这时候只需要返回数组0就是我们要的结果。
代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
int k = 1, length = lists.length;
while (true) {
for (int i=0; i<length; i=i+2*k) {
if (i+k < length) {
lists[i] = mergeList(lists[i], lists[i+k]);
}
}
k *= 2;
if (k >= length) break;
}
return lists[0];
}
private ListNode mergeList(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeList(l1.next, l2);
return l1;
} else {
l2.next = mergeList(l1, l2.next);
return l2;
}
}
}
结果分析
leetcode给出的击败率88%，耗时9ms，时间和空间复杂度不太会分析暂时不弄了，但是整体的时间复杂度是O(n)级别的，空间复杂度略大。
