数据结构与算法——Java实现 30.合并多个有序链表 小顶堆实现
后来我们都走了很久，远到提及往事时，
总会加上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;
}
}
}