LeetCode 上最難的鏈表算法題,沒有之一!

LeetCode 上最難的鏈表算法題,沒有之一!

題目來源於 LeetCode 第 23 號問題:合併 K 個排序鏈表。

該題在 LeetCode 官網上有關於鏈表的問題中標註為最難的一道題目:難度為 Hard ,通過率在鏈表 Hard 級別目前最低。

題目描述

合併 k 個排序鏈表,返回合併後的排序鏈表。請分析和描述算法的複雜度。

示例:

輸入:
[
1->4->5,
1->3->4,
2->6
]
輸出: 1->1->2->3->4->4->5->6

輸入

LeetCode 上最難的鏈表算法題,沒有之一!

圖一

輸出

LeetCode 上最難的鏈表算法題,沒有之一!

圖二

題目分析一

這裡需要將這 k 個排序鏈表整合成一個排序鏈表,也就是說有多個輸入,一個輸出,類似於漏斗一樣的概念。

因此,可以利用最小堆的概念。如果你對堆的概念不熟悉,

可以戳這先了解一下~

取每個 Linked List 的最小節點放入一個 heap 中,排序成最小堆。然後取出堆頂最小的元素,放入輸出的合併 List 中,然後將該節點在其對應的 List 中的下一個節點插入到 heap 中,循環上面步驟,以此類推直到全部節點都經過 heap。

由於 heap 的大小為始終為 k ,而每次插入的複雜度是 logk ,一共插入了 nk 個節點。時間複雜度為 O(nklogk),空間複雜度為O(k)。

代碼實現

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//用heap(堆)這種數據結構,也就是 java 裡面的 PriorityQueue
PriorityQueue<listnode> pq = new PriorityQueue<>(new Comparator<listnode>() {
public int compare(ListNode a, ListNode b) {
return a.val-b.val;
}
});
ListNode ret = null, cur = null;
for(ListNode node: lists) {
if(null != node) {
pq.add(node);
}
}
while(!pq.isEmpty()) {
ListNode node = pq.poll();
if(null == ret) {
ret = cur = node;
}
else {
cur = cur.next = node;

}
if(null != node.next) {
pq.add(node.next);
}
}
return ret;
}
}
/<listnode>/<listnode>

題目分析二

這道題需要合併 k 個有序鏈表,並且最終合併出來的結果也必須是有序的。如果一開始沒有頭緒的話,可以先從簡單的開始:合併 兩 個有序鏈表

合併兩個有序鏈表:將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例:

輸入:1->2->4, 1->3->4
輸出:1->1->2->3->4->4

這道題目按照題目描述做下去就行:新建一個鏈表,比較原始兩個鏈表中的元素值,把較小的那個鏈到新鏈表中即可。需要注意的一點時由於兩個輸入鏈表的長度可能不同,所以最終會有一個鏈表先完成插入所有元素,則直接另一個未完成的鏈表直接鏈入新鏈表的末尾。

所以代碼實現很容易寫:

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//新建鏈表
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
// 注意點:當有鏈表為空時,直接連接另一條鏈表
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummyHead.next;
}

現在回到一開始的題目:合併 K 個排序鏈表。

合併 K 個排序鏈表合併兩個有序鏈表 的區別點在於操作有序鏈表的數量上,因此完全可以按照上面的代碼思路來實現合併 K 個排序鏈表。

這裡可以參考

歸併排序 的分治思想,將這 K 個鏈表先劃分為兩個 K/2 個鏈表,處理它們的合併,然後不停的往下劃分,直到劃分成只有一個或兩個鏈表的任務,開始合併。

LeetCode 上最難的鏈表算法題,沒有之一!

歸併-分治

代碼實現

根據上面的動畫,實現代碼非常簡單也容易理解,先劃分,直到不能劃分下去,然後開始合併。

class Solution {
public ListNode mergeKLists(ListNode[] lists){
if(lists.length == 0)
return null;
if(lists.length == 1)
return lists[0];
if(lists.length == 2){
return mergeTwoLists(lists[0],lists[1]);
}
int mid = lists.length/2;
ListNode[] l1 = new ListNode[mid];
for(int i = 0; i < mid; i++){
l1[i] = lists[i];
}
ListNode[] l2 = new ListNode[lists.length-mid];
for(int i = mid,j=0; i < lists.length; i++,j++){
l2[j] = lists[i];
}
return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
}


分享到:


相關文章: