23 合并k个有序链表
[toc]
题目：https://leetcode-cn.com/problems/merge-k-sorted-lists/
请你将所有链表合并到一个升序链表中，返回合并后的链表。
准备代码
// Date: 2020-11-07 16:41:12
/// FilePath: /algorithm/leetCode/链表/list_node.dart
/// Description: 链表的基类
///
class ListNode {
int val;
ListNode next;
ListNode({this.val, this.next});
@override
String toString() {
ListNode preNode = this;
String resultStr = '${preNode.val}';
while (preNode.next != null) {
preNode = preNode.next;
resultStr = '$resultStr->${preNode.val}';
}
return resultStr;
}
///
/// Author: liyanjun
/// description: 传入数组生成链表
///
static ListNode changeListToNode(List<int> list) {
if (list == null || list.length == 0) {
return null;
}
ListNode listNode = ListNode();
ListNode preNode = listNode;
for (var i = 0; i < list.length; i++) {
if (i == 0) {
listNode.val = list[i];
preNode = listNode;
} else {
preNode.next = ListNode(val: list[i]);
preNode = preNode.next;
}
}
return listNode;
}
}
思路
思路1：最笨的方法
- 将所有节点添加到一个数组中
- 对数组中的节点从小到大进行排序
- 从数组中从小到大依次取出节点，串成链表
代码
///
/// Author: liyanjun
/// description:方法一 最笨的方法
/// 1. 将所有节点添加到一个数组中
// 2. 对数组中的节点从小到大进行排序
// 3. 从数组中从小到大依次取出节点，串成链表
/// 时间复杂度 O(n logn) 空间复杂度 O（n）
ListNode mergeKLists1(List<ListNode> lists) {
if (lists == null || lists.length == 0) return null;
List<ListNode> nodes = [];
//存入nodes O(n)
for (var list in lists) {
while (list != null) {
nodes.add(list);
list = list.next;
}
}
//对nodes进行排序 O(n logn)
nodes.sort((v1, v2) => (v1.val - v2.val));
ListNode head = ListNode(); //虚头节点
ListNode cur = head;
// O(n)
for (var node in nodes) {
cur = cur.next = node;
}
return head.next;
}
思路2：逐一比较
- 遍历lists
- 取到当前lists中最小的结点
- 把改结点的下一节点作为该结点的起点
代码
///
/// Author: liyanjun
/// description: 1. 遍历lists
// 2. 取到当前lists中最小的结点
// 3. 把改结点的下一节点作为该结点的起点
// O[kn]
///
ListNode mergeKLists2(List<ListNode> lists) {
if (lists == null || lists.length == 0) return null;
//虚拟头结点
ListNode head = ListNode();
ListNode cur = head;
while (true) {
//最小链表所在索引
int minIndex = -1;
for (var i = 0; i < lists.length; i++) {//k
if (lists[i] == null) continue;
if (minIndex == -1 || lists[i].val < lists[minIndex].val) {
minIndex = i;
}
}
if(minIndex == -1)break;//标识所有都已经串联起来
cur = cur.next = lists[minIndex];
lists[minIndex] = lists[minIndex].next;//n
}
return head.next;
}
思路3：两两合并
- 两两合并做一个合并好的链表A
- 链表A与下一个链表合并
代码
///
/// Author: liyanjun
/// description:方法而 迭代 复杂度 O[kn]
///
ListNode mergeKLists3(List<ListNode> lists) {
if (lists == null || lists.length == 0) return null;
//虚拟头结点
ListNode head;
for (ListNode listNode in lists) {//k
head = mergeTwoLists(head, listNode);//将k次的时间 1 + (n/k+n/k) +(2*n/k+n/k)+...+((k-1)*(n/k)+n/k=kn
}
return head.next;
}
///
/// Author: liyanjun
/// description: 合并2个
///
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head;
ListNode cur;
cur = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur = cur.next = l1;
l1 = l1.next;
} else {
cur = cur.next = l2;
l2 = l2.next;
}
}
if (l1 == null) {
cur.next = l2;
} else if (l2 == null) {
cur.next = l1;
}
return head.next;
}
思路4：优先级队列
- 思路二演变而来
- 优先级度列小顶堆实现
O(nlogk)，空间复杂度：O(k)
代码
dart没有优先级队列数据结构，后面自己写，补充
思路5：分支策略
- 思路二演变而来
-
两两合并
image.png
时间复杂度：O(nlogk)
因为进行了logk轮，每一轮都是时间复杂度n
代码
///
/// Author: liyanjun
/// description:分治思想
/// 思路3演变而来
///
///
ListNode mergeKLists5(List<ListNode> lists) {
if (lists == null || lists.length == 0) return null;
int step = 1;
while (step < lists.length) {
int nextStep = step << 1;//每次要跳这么多进行合并
//优先级队列的数据结构
for (var i = 0; i + step < lists.length; i += nextStep) {
mergeTwoLists(lists[i], lists[i + step]);
}
step = nextStep;
}
return lists[0];
}
优化
根据归并排序优化
///
/// Author: liyanjun
/// description:
/// 思路5，不过用归并排序实现
///
///
ListNode mergeKLists6(List<ListNode> lists) {
if (lists == null || lists.length == 0) return null;
return _mergedive(lists, 0, lists.length-1);
}
///
/// Author: liyanjun
/// description: 归并思想 分
///
ListNode _mergedive(List<ListNode> lists, int begin, int end) {
if(begin == end){
return lists[begin];
}
int mid = (begin+end)>>1;
ListNode listNodeLeft= _mergedive(lists,begin,mid);
ListNode listNodeRight= _mergedive(lists,mid+1,end);
return mergeTwoLists(listNodeLeft,listNodeRight);
}
