后来我们都走了很久，远到提及往事时，
总会加上once upon a time
—— 24.10.6
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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
思路
将k个升序链表依次遍历，因为他们升序，所以比较三个升序链表的第一个元素值，将三个元素中的最小值放入堆顶，然后被放入元素的那个链表的指针向后移动一位，直到k个升序链表中的所有元素都被进行比较移入堆中，由于是小顶堆，所以小的元素会移动在前，形成一个升序链表，最终得出合并后的升序链表
小顶堆实现
public class MinHeap {ListNode[] array;int size;public MinHeap(int capacity) {array = new ListNode[capacity];}public boolean offer(ListNode node) {if (isFull()){return false;}int child = size;size++;int parent = (child - 1) / 2;while (child >0 && node.val < array[parent].val) {array[child] = array[parent];child = parent;parent = (child - 1) / 2;}array[child] = node;return true;}public ListNode poll() {if (isEmpty()) {return null;}swap(0,size-1);size--;ListNode e = array[size];array[size] = null;// 下潜down(0);return e;}private void down(int parent) {int left = 2 * parent+1;int right = left + 1;// 假设父元素优先级最高int max = parent;if (left < size && array[left].val < array[max].val) {max = left;}if (right < size && array[right].val < array[max].val) {max = right;}// 有孩子优先级大于父节点if (max != parent) {swap(max,parent);down(max);}}private void swap(int i, int j) {ListNode temp = array[i];array[i] = array[j];array[j] = temp;}public boolean isEmpty() {return size == 0;}public boolean isFull(){return size == array.length;}
}
主函数
public class LeetCode23MergeMoreList {public ListNode mergeKLists(ListNode[] lists) {MinHeap heap = new MinHeap(lists.length);// 1.将链表的头结点加入小顶堆for (ListNode node : lists) {if (node != null) {heap.offer(node);}}// 2.不断从堆顶移除最小元素，加入新链表ListNode s = new ListNode(-1,null);ListNode cur = s;while (!heap.isEmpty()) {ListNode node = heap.poll();cur.next = node;cur = node;if (cur.next != null) {heap.offer(node.next);}}return s.next;}public static void main(String[] args) {ListNode[] lists = {ListNode.of(1,4,5),ListNode.of(2,3,6),ListNode.of(3,4,7),};ListNode m = new LeetCode23MergeMoreList().mergeKLists(lists);System.out.println(m);}
}
力扣
/*** 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) {MinHeap heap = new MinHeap(lists.length);// 1.将链表的头结点加入小顶堆for (ListNode node : lists) {if (node != null) {heap.offer(node);}}// 2.不断从堆顶移除最小元素，加入新链表ListNode s = new ListNode(-1,null);ListNode cur = s;while (!heap.isEmpty()) {ListNode node = heap.poll();cur.next = node;cur = node;if (cur.next != null) {heap.offer(node.next);}}return s.next;}static class MinHeap {ListNode[] array;int size;public MinHeap(int capacity) {array = new ListNode[capacity];}public boolean offer(ListNode node) {if (isFull()){return false;}int child = size;size++;int parent = (child - 1) / 2;while (child >0 && node.val < array[parent].val) {array[child] = array[parent];child = parent;parent = (child - 1) / 2;}array[child] = node;return true;}public ListNode poll() {if (isEmpty()) {return null;}swap(0,size-1);size--;ListNode e = array[size];array[size] = null;// 下潜down(0);return e;}private void down(int parent) {int left = 2 * parent+1;int right = left + 1;// 假设父元素优先级最高int max = parent;if (left < size && array[left].val < array[max].val) {max = left;}if (right < size && array[right].val < array[max].val) {max = right;}// 有孩子优先级大于父节点if (max != parent) {swap(max,parent);down(max);}}private void swap(int i, int j) {ListNode temp = array[i];array[i] = array[j];array[j] = temp;}public boolean isEmpty() {return size == 0;}public boolean isFull(){return size == array.length;}}}
