今天和大家聊的问题叫做合并K个升序链表，我们先来看题面：
https://leetcode-cn.com/problems/merge-k-sorted-lists/
Given an array of linked-lists lists, each linked list is sorted in ascending order.
Merge all the linked-lists into one sort linked-list and return it.
题意
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
样例
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2： 输入：lists = [] 输出：[] 示例 3： 输入：lists = [[]] 输出：[]
题解
暴力破解法：其中n为lists数组的长度，m为lists数组中链表总节点个数
public class Solution { public ListNode mergeKLists(ListNode[] lists) { int n; if (null == lists || (n = lists.length) == 0) { return null; } ListNode[] curs = new ListNode[n]; for (int i = 0; i < n; i++) { curs[i] = lists[i]; } ListNode dummyHead = new ListNode(-1), cur = dummyHead; do { //index索引的作用是寻找一个非空的链表 int index = 0; for (int i = 0; i < n; i++) { if (curs[i] != null) { break; } index++; } if (index == n) { break; } int minIndex = index; for (int i = index + 1; i < n; i++) { if (curs[i] != null && curs[i].val < curs[minIndex].val) { minIndex = i; } } cur.next = curs[minIndex]; cur = cur.next; curs[minIndex] = curs[minIndex].next; } while (true); return dummyHead.next; } }
优先队列：其中m为lists数组中链表总节点个数。
public class Solution { public ListNode mergeKLists(ListNode[] lists) { int n; if (null == lists || (n = lists.length) == 0) { return null; } PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int i = 0; i < n; i++) { ListNode cur = lists[i]; while (cur != null) { pq.add(cur.val); cur = cur.next; } } ListNode dummyHead = new ListNode(-1), cur = dummyHead; while (!pq.isEmpty()) { cur.next = new ListNode(pq.poll()); cur = cur.next; } return dummyHead.next; } }
两两合并链表：其中n为lists数组的长度，m为lists数组中链表总节点个数
public class Solution { public ListNode mergeKLists(ListNode[] lists) { int n; if (null == lists || (n = lists.length) == 0) { return null; } ListNode result = lists[0]; for (int i = 1; i < n; i++) { result = mergeTwoLists(result, lists[i]); } return result; } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode cur1 = l1, cur2 = l2, dummyHead = new ListNode(-1), cur = dummyHead; while (cur1 != null || cur2 != null) { if (cur1 == null) { cur.next = cur2; cur2 = cur2.next; } else if (cur2 == null) { cur.next = cur1; cur1 = cur1.next; } else if (cur1.val > cur2.val) { cur.next = cur2; cur2 = cur2.next; } else { cur.next = cur1; cur1 = cur1.next; } cur = cur.next; } return dummyHead.next; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
