【問題描述】23.合并K個排序鏈表

合并 k 個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復雜度。 示例: 輸入: [1->4->5,1->3->4,2->6 ] 輸出: 1->1->2->3->4->4->5->6

【解答思路】

1. 兩兩合并

public class Solution2 {public ListNode mergeKLists(ListNode[] lists) {int size = lists.length;if (size == 0) {return null;}ListNode res = lists[0];for (int i = 1; i < size; i++) {if (lists[i] != null) {res = mergeTwoSortLinkedList(res, lists[i]);}}return res;}private ListNode mergeTwoSortLinkedList(ListNode list1, ListNode list2) {ListNode dummyNode = new ListNode(-1);ListNode p1 = list1;ListNode p2 = list2;ListNode curNode = dummyNode;// 兩者都不為空的時候，才有必要進行比較while (p1 != null && p2 != null) {if (p1.val < p2.val) {// 指針修改發生在這里curNode.next = p1;p1 = p1.next;} else {// 指針修改發生在這里curNode.next = p2;p2 = p2.next;}curNode = curNode.next;}// 跳出循環是因為 p1 == null 或者 p2 == nullif (p1 == null) {curNode.next = p2;}if (p2 == null) {curNode.next = p1;}return dummyNode.next;} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/tan-xin-suan-fa-you-xian-dui-lie-fen-zhi-fa-python/

2. 分治法

想清楚數據結構 ListNode[] 只存了頭節點
1、先一分為二，分別“遞歸地”解決了與原問題同結構，但規模更小的兩個子問題；
2、再考慮如何合并，這個合并的過程也是一個遞歸方法（同 LeetCode 第 21 題：合并兩個有序鏈表）。
時間復雜度：O(NlogN)

import java.util.Comparator; import java.util.PriorityQueue;class ListNode {int val;ListNode next;ListNode(int x) {val = x;} //測試使用ListNode(Integer[] nums) {ListNode currNode = this;currNode.val = nums[0];for (int i = 1; i < nums.length; i++) {currNode.next = new ListNode(nums[i]);currNode = currNode.next;}} //測試使用@Overridepublic String toString() {ListNode currNode = this;StringBuilder s = new StringBuilder();while (currNode != null) {s.append(currNode.val);s.append(" -> ");currNode = currNode.next;}// 最后添加一個 NULL 標志表示添加到末尾了s.append("NULL");return s.toString();} }public class Solution {public ListNode mergeKLists(ListNode[] lists) {int len = lists.length;if (len == 0) {return null;}return mergeKLists(lists, 0, len - 1);}public ListNode mergeKLists(ListNode[] lists, int l, int r) {// 思考這里為什么取等于？這是因為根據下文對 mergeKLists 的遞歸調用情況，區間最窄的時候，只可能是左右端點重合if (l == r) {return lists[l];}int mid = (r - l) / 2 + l;ListNode l1 = mergeKLists(lists, l, mid);ListNode l2 = mergeKLists(lists, mid + 1, r);return mergeTwoSortedListNode(l1, l2);}private ListNode mergeTwoSortedListNode(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}if (l1.val < l2.val) {l1.next = mergeTwoSortedListNode(l1.next, l2);return l1;}l2.next = mergeTwoSortedListNode(l1, l2.next);return l2;} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/tan-xin-suan-fa-you-xian-dui-lie-fen-zhi-fa-python/

3. 貪心算法、優先隊列 （最小堆）

時間復雜度：O(NlogN) 空間復雜度：O(N)

import java.util.Comparator; import java.util.PriorityQueue;class ListNode {int val;ListNode next;ListNode(int x) {val = x;} //n條鏈表合成一條 測試使用ListNode(Integer[] nums) {ListNode currNode = this;currNode.val = nums[0];for (int i = 1; i < nums.length; i++) {currNode.next = new ListNode(nums[i]);currNode = currNode.next;}} //測試使用 @Overridepublic String toString() {ListNode currNode = this;StringBuilder s = new StringBuilder();while (currNode != null) {s.append(currNode.val);s.append(" -> ");currNode = currNode.next;}// 最后添加一個 NULL 標志表示添加到末尾了s.append("NULL");return s.toString();} }public class Solution {public ListNode mergeKLists(ListNode[] lists) {int len = lists.length;if (len == 0) {return null;}PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(len, Comparator.comparingInt(a -> a.val));/*@Overridepublic int compare(ListNode o1, ListNode o2) {if (o1.val < o2.val) return -1;else if (o1.val == o2.val) return 0;else return 1;}*/ListNode dummyNode = new ListNode(-1);ListNode curNode = dummyNode;for (ListNode list : lists) {if (list != null) {// 這一步很關鍵，不能也沒有必要將空對象添加到優先隊列中priorityQueue.add(list);}}while (!priorityQueue.isEmpty()) {// 優先隊列非空才能出隊ListNode node = priorityQueue.poll();// 當前節點的 next 指針指向出隊元素curNode.next = node;// 當前指針向前移動一個元素，指向了剛剛出隊的那個元素curNode = curNode.next;if (curNode.next != null) {// 只有非空節點才能加入到優先隊列中priorityQueue.add(curNode.next);}}return dummyNode.next;}public static void main(String[] args) {Integer[] nums1 = {1, 4, 5};Integer[] nums2 = {1, 3, 4};Integer[] nums3 = {2, 6};ListNode head1 = new ListNode(nums1);ListNode head2 = new ListNode(nums2);ListNode head3 = new ListNode(nums3);ListNode[] lists = new ListNode[3];lists[0] = head1;lists[1] = head2;lists[2] = head3;Solution solution = new Solution();ListNode mergeKLists = solution.mergeKLists(lists);System.out.println(mergeKLists);} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/tan-xin-suan-fa-you-xian-dui-lie-fen-zhi-fa-python/

【總結】

1.遞歸思想

1、數組的排序方法要很清楚，這一點是遷移到鏈表上，發現只有歸并排序適用；
2、歸并排序其實就是分而治之；
3、還要清楚兩個排序鏈表是怎么合并的（可以遞歸也可以非遞歸用雙指針去穿針引線）。
如果這些所以就很自然遷移到合并 K 個排序鏈表。

2.鏈表

• “遞歸”、“分治”
• “穿針引線” 優先隊列 堆

3.PriorityQueue

1>PriorityQueue是一種無界的，線程不安全的隊列（無鎖）
2>PriorityQueue是一種通過數組實現的，并擁有優先級的隊列
3>PriorityQueue存儲的元素要求必須是可比較的對象Comparator（數量+比較對象）， 如果不是就必須明確指定比較器

優先隊列java解析與用法：https://www.jb51.net/article/84371.htm
優先隊列源碼解析：https://www.cnblogs.com/CarpenterLee/p/5488070.html
解題解析：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/tan-xin-suan-fa-you-xian-dui-lie-fen-zhi-fa-python/

總結

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题[第23题][合并K个排序链表][分治][优先队列]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。