本题是本人字节跳动一面考的算法题
原题是有序数组，一时没想到怎么解决数组的问题，但是如果给的是有序链表数组，则可以用下面的方法解决
可以利用最小堆完成，时间复杂度是O(nklogk)，具体过程如下：
创建一个大小为k的最小堆，堆中元素为k个链表中的每个链表的第一个元素
重复下列步骤
每次从堆中取出最小元素（堆顶元素），并将其存入输出数组中
用堆顶元素所在链表元素的下一元素将堆顶元素替换掉，
初始化最小堆的时间复杂度O（k），总共有kn次循环，每次循环调整最小堆的时间复杂度是O（logk）
，所以总的时间复杂度是O（knlogk）
import java.util.ArrayList;import parator;import java.util.PriorityQueue;public class 合并K个有序数组 {public static ListNode merge(ListNode[] arr) {int k = arr.length;ListNode dumy = new ListNode(-1);ListNode p = dumy;PriorityQueue<ListNode> maxHeap = new PriorityQueue<>(k, new Comparator<ListNode>() {@Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val - o2.val;}});for (int i = 0; i < k; i++)maxHeap.offer(arr[i]);while (!maxHeap.isEmpty()) {ListNode tmp = maxHeap.poll();if (tmp.next != null)maxHeap.offer(tmp.next);p.next = tmp;p = p.next;}return dumy.next;}//测试代码public static void main(String[] args) {ListNode a1 = new ListNode(1);a1.next = new ListNode(2);a1.next.next = new ListNode(3);a1.next.next.next = new ListNode(100);ListNode b1 = new ListNode(1);b1.next = new ListNode(2);b1.next.next = new ListNode(3);ListNode c1 = new ListNode(2);c1.next = new ListNode(3);c1.next.next = new ListNode(5);ListNode[] arr = {a1, b1, c1};ListNode res = merge(arr);while (res!= null) {System.out.print(res.val + " ");res = res.next;}}}
