JAVA练习302- 合并K个排序链表

题目概览

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：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 = [[]]输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]按升序排列
• lists[i].length的总和不超过10^4

来源：23. 合并 K 个升序链表 - 力扣（LeetCode）

解题分析

方法：二分 + 归并排序

lists 里的链表都是排好序的，这和归并排序类似，只需要两两链表挨个元素进行比较，不断连接小的节点即可。而两两比较可以用二分法，将数组拆分成多个小数组，然后从小的数组开始不断合并

时间复杂度：O(logk * nk)
空间复杂度：O(logk)

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { int n = lists.length; if (n == 0) { return null; } return mergeKLists(lists, 0, n - 1); } public ListNode mergeKLists(ListNode[] lists, int i, int j) { if (i == j) { return lists[i]; } if (i + 1 == j) { return merge(lists[i], lists[j]); } int mid = (i + j) / 2; return merge(mergeKLists(lists, i, mid), mergeKLists(lists, mid + 1, j)); } public ListNode merge(ListNode a, ListNode b) { ListNode res = new ListNode(), pre = res; while(a != null && b != null) { if (a.val <= b.val) { pre.next = a; a = a.next; } else { pre.next = b; b = b.next; } pre = pre.next; } if (a != null) { pre.next = a; } else if (b != null) { pre.next = b; } return res.next; } }