当前位置：首页 > news >正文

详解 leetcode_078. 合并K个升序链表.小顶堆实现

news 2025/6/26 10:27:51


/*** 构造单链表节点*/
class ListNode{int value;//节点值ListNode next;//指向后继节点的引用public ListNode(){}public ListNode(int value){this.value=value;}public ListNode(int value,ListNode next){this.value=value;this.next=next;}
}package com.ag;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;/***  leetcode_078. 合并K个升序链表*  解题思路：*  1.定义小根堆的大小为K，然后从每个链表拿一个元素进来构造最小堆*  2.取走堆顶元素（一定是最小值）插入到新链表的表尾，然后将该元素所在的链表再拿一个元素进来，重新构造小顶堆**/
public class MergeKASCList {public ListNode mergeKLists(List<ListNode> lists){//1.判断边界if(lists==null||lists.size()==0){return null;}//2.构造最小堆Queue<ListNode> minHeap=new PriorityQueue<>((o1, o2) -> o1.value-o2.value);for (ListNode listNode : lists) {if(listNode!=null){minHeap.offer(listNode);//元素入堆}}//3.构造合并后的新链表ListNode head=new ListNode(0);ListNode tail=head;while (!minHeap.isEmpty()){//堆顶元素出堆,获取链表最小节点，加入新链表队尾tail.next=minHeap.poll();tail=tail.next;if(tail.next!=null){minHeap.offer(tail.next);//最小链表节点的下一个节点加入最小堆 (重新构造小顶堆)}}return head.next;}public static void main(String[] args) {List<ListNode> lists=new ArrayList<>();//1.初始化各个节点ListNode node1=new ListNode(1);ListNode node2=new ListNode(4);ListNode node3=new ListNode(5);ListNode node4=new ListNode(1);ListNode node5=new ListNode(3);ListNode node6=new ListNode(4);ListNode node7=new ListNode(2);ListNode node8=new ListNode(6);//2.构建节点之间的引用node1.next=node2;node2.next=node3;node4.next=node5;node5.next=node6;node7.next=node8;//打印链表
//        printLinkedList(node1);
//        printLinkedList(node4);
//        printLinkedList(node7);//3.将链表头节点添加到listlists.add(node1);lists.add(node4);lists.add(node7);//4.合并链表MergeKASCList mergeKASCList=new MergeKASCList();ListNode listNode=mergeKASCList.mergeKLists(lists);//5.打印合并后的链表printLinkedList(listNode);}/*** 打印链表* @param head*/public static void printLinkedList(ListNode head) {List<String> list = new ArrayList<>();while (head != null) {list.add(String.valueOf(head.value));head = head.next;}System.out.println(String.join(" -> ", list));}
}