題目描述
23.合并K個排序鏈表
合并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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199365.html
標籤：其他
上一篇：第11屆藍橋杯省賽模擬 螺旋矩陣