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：最笨的方法

1. 将所有节点添加到一个数组中
2. 对数组中的节点从小到大进行排序
3. 从数组中从小到大依次取出节点，串成链表

代码

///
/// 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：逐一比较

1. 遍历lists
2. 取到当前lists中最小的结点
3. 把改结点的下一节点作为该结点的起点

代码

///
/// 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：两两合并

1. 两两合并做一个合并好的链表A
2. 链表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：优先级队列

1. 思路二演变而来
2. 优先级度列小顶堆实现
   O(nlogk)，空间复杂度：O(k)

代码

dart没有优先级队列数据结构，后面自己写，补充

思路5：分支策略

1. 思路二演变而来

2. 两两合并

   
   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);
}