题目描述
合并k个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例：
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
题目解析
方法一：暴力法
解题思路
合并K个排序链表，首先我们直接采用暴力法去解决，将链表所有节点的val值放入一个List中，然后将这个List进行排序，根据排序后的List重新构建新链表。
代码示例
Java：
/**
* 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 == null || lists.length == 0) return null;
// 1. 将链表节点放入一个List中
List<Integer> arr = new ArrayList<Integer>();
for (int i = 0; i < lists.length; i++) {
ListNode cur = lists[i];
while(cur != null) {
arr.add(cur.val);
cur = cur.next;
}
}
// 2. 排序
Collections.sort(arr);
// 3. 重新构建链表
ListNode res = new ListNode(0);
ListNode cur = res;
for(int i = 0; i < arr.size(); i++) {
ListNode node = new ListNode(arr.get(i));
cur.next = node;
cur = cur.next;
}
return res.next;
}
}
复杂度分析
时间复杂度：O(N * log(N)), N代表所有链表节点数量。
- 遍历所有值需要花费O(N)时间
- 稳定的排序算法花费N * log(N)时间
- 重新构建链表需要花N * log(N)时间
空间复杂度：O(N)
方法二：堆排序法
解题思路
采用堆的方式来进行链表节点的排序，创建一个大小为K的小根堆，首先将K个链表的头指针插入到堆中，然后取出堆顶元素，同时将堆顶元素的下一个节点插入到最小堆中，然后循环该操作直至链表节点全部遍历完成。
代码示例
Java：
/**
* 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 == null || lists.length == 0) return null;
// 1. 初始化小根堆
PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {
public int compare(ListNode o1, ListNode o2) {
return (o1.val - o2.val);
}
});
for(int i = 0; i < lists.length; i++) {
if (lists[i] != null) queue.add(lists[i]);
}
// 2. 取出堆顶元素，并将堆顶元素的下一节点插入小根堆
ListNode res = new ListNode(0);
ListNode cur = res;
while(!queue.isEmpty()) {
ListNode top = queue.poll();
if (top.next != null) {
queue.add(top.next);
}
cur.next = top;
cur = cur.next;
}
return res.next;
}
}
复杂度分析
时间复杂度：O(N * log(K))，N代表所有链表节点数量，K代表链表的个数。
空间复杂度：O(K)
方法三：分治法
解题思路
我们将K个链表对半划分，先合并前K/2个链表，再合并后K/2个链表，然后将前K/2个链表合并成的链表再与后K/2个链表合并的链表进行合并，得到最终结果。
在处理前K/2个和后K/2个链表时，就跟上述方法思路一致，通过递归的方式不停的将链表进行划分，直到链表无法继续划分为止，将链表返回给递归的上一层进行两两合并。
分治思路：划分子问题 --> 合并子问题结果【递归实现】
代码示例
Java：
/**
* 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 == null || lists.length == 0) return null;
return divide(lists, 0, lists.length-1);
}
public ListNode divide(ListNode[] lists, int lo, int hi) {
if (lo == hi) return lists[lo];
int mid = lo + (hi - lo) / 2;
ListNode left = divide(lists, lo, mid);
ListNode right = divide(lists, mid + 1, hi);
return merge(left, right);
}
public ListNode merge(ListNode l1, ListNode l2) {
if(l1 == null || l2 == null) {
return (l1 == null) ? l2 : l1;
}
if(l1.val <= l2.val) {
l1.next = merge(l1.next,l2);
return l1;
} else {
l2.next = merge(l1, l2.next);
return l2;
}
}
}
复杂度分析
时间复杂度：O(N * log(K))，N代表所有链表节点数量，K代表链表的个数。
空间复杂度：O(K)
