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.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[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; } }