前言：📫 作者简介：小明java问道之路，专注于研究计算机底层，就职于金融公司后端高级工程师，擅长交易领域的高安全/可用/并发/性能的设计和架构📫
🏆 Java领域优质创作者、阿里云专家博主、华为云享专家🏆
🔥 如果此文还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦
本文导读
字节跳动企业题库，链表系列，因为有leetcode会员能看到企业出题频率，那我们从出题频率最高刷到最低，题目有 23. 合并K个有序链表
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 = [[]] 输出：[]
【暴力、递归、迭代】图解：
代码详解，逐行注释：
/*** 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; }* }*/classSolution { /*K 指针：K 个指针分别指向K条链表;每次O(K)比较K个指针min, 时间复杂度O(NK)*/publicListNodemergeKLists(ListNode[] lists) { intk=lists.length; ListNodedummyHead=newListNode(0); ListNodetail=dummyHead; while (true) { ListNodeminNode=null; intminPointer=-1; for (inti=0; i<k; i++) { if (lists[i] ==null) { continue; } if (minNode==null||lists[i].val<minNode.val) { minNode=lists[i]; minPointer=i; } } if (minPointer==-1) { break; } tail.next=minNode; tail=tail.next; lists[minPointer] =lists[minPointer].next; } returndummyHead.next; } }
classSolution { /*两两合并 - 迭代*/publicListNodemergeKLists(ListNode[] lists) { if (lists.length==0) { returnnull; } intk=lists.length; while (k>1) { intidx=0; for (inti=0; i<k; i+=2) { if (i==k-1) { lists[idx++] =lists[i]; } else { lists[idx++] =merge2Lists(lists[i], lists[i+1]); } } k=idx; } returnlists[0]; } } classSolution { /*两两合并 - 递归*/publicListNodemergeKLists(ListNode[] lists) { if (lists.length==0) { returnnull; } returnmerge(lists, 0, lists.length-1); } privateListNodemerge(ListNode[] lists, intlo, inthi) { if (lo==hi) { returnlists[lo]; } intmid=lo+ (hi-lo) /2; ListNodel1=merge(lists, lo, mid); ListNodel2=merge(lists, mid+1, hi); returnmerge2Lists(l1, l2); } }
