Loading... # 分治 23.合并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` ### 代码 ```java package ski.mashiro.leetcode; import java.util.ArrayList; import java.util.Comparator; import java.util.List; public class _23 { /** * 23. 合并K个升序链表 * <p> * 给你一个链表数组，每个链表都已经按升序排列。 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。 */ public static void main(String[] args) { ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5))); ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4))); ListNode l3 = new ListNode(2, new ListNode(6)); ListNode listNode = mergeKLists(new ListNode[]{l1, l2, l3}); while (listNode != null) { System.out.print(listNode.val + ", "); listNode = listNode.next; } } /** * 分治 * 每次将两个链表合并成一个 */ public static ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); } private static ListNode merge(ListNode[] lists, int left, int right) { // 左右指针指向同一元素，直接返回 if (left == right) { return lists[left]; } // 因为mid + 1，有可能发生左指针大于右指针的情况 // 返回null if (left > right) { return null; } // 注释的是问题代码，目测是在向下舍入的时候有精度问题，导致无限递归 // int mid = (right - left) >> 1 + left; int mid = (left + right) >> 1; // 递归调用，递归返回数组的元素或是null，两者再进行合并，返回到上层递归称为参数 return mergeTwoListNode(merge(lists, left, mid), merge(lists, mid + 1, right)); } /** * 法二 * 新建一个链表，每次将新链表和数组内的一个链表合并 */ public static ListNode mergeKLists2(ListNode[] lists) { List<Integer> list = new ArrayList<>(lists.length * 5); ListNode rs = null; for (ListNode listNode : lists) { rs = mergeTwoListNode(rs, listNode); } return rs; } private static ListNode mergeTwoListNode(ListNode list1, ListNode list2) { ListNode rs = new ListNode(); ListNode cur = rs; while (list1 != null || list2 != null) { if (list1 != null && list2 != null) { if (list1.val < list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } } else if (list1 != null) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } return rs.next; } /** * 法三 * 转换成集合处理 */ public static ListNode mergeKLists3(ListNode[] lists) { List<Integer> list = new ArrayList<>(lists.length * 5); for (ListNode listNode : lists) { while (listNode != null) { list.add(listNode.val); listNode = listNode.next; } } list.sort(Comparator.comparingInt(o -> o)); ListNode rs = new ListNode(); ListNode cur = rs; for (Integer item : list) { cur.next = new ListNode(item); cur = cur.next; } return rs.next; } private static class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } } ``` 最后修改：2022 年 12 月 20 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 本作品采用 CC BY-NC-SA 4.0 International License 进行许可。
