LeetCode合并K个排序链表（题号23）代码超时问题求助

你的代码出现超时的核心原因是时间复杂度太高：每次循环都要遍历所有K个链表找当前最小值，总时间复杂度为O(N*K)（N是所有链表的总节点数），当K较大时，这个复杂度会导致超时。

原代码的其他问题 #

• 循环条件逻辑错误：while (!emptyCheck(lists)&&lists.length!=0) 中，emptyCheck返回true表示还有非空链表，取反后!emptyCheck意味着所有链表都已为空，这时候循环根本不应该执行，会导致结果异常或逻辑错误。
• 不必要的节点创建：每次都新建ListNode对象，其实可以直接复用原链表的节点，减少内存开销和对象创建的时间损耗。

优化方案：使用最小堆（优先队列） #

用优先队列维护当前所有非空链表的头节点，每次取出最小值节点的时间复杂度为O(logK)，总时间复杂度降为O(NlogK)，可以有效避免超时。

优化后的代码如下：

import java.util.PriorityQueue;

/**
 * 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; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 定义最小堆，按节点val升序排序
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        // 将所有非空链表的头节点加入堆
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (!minHeap.isEmpty()) {
            // 取出当前最小的节点
            ListNode minNode = minHeap.poll();
            current.next = minNode;
            current = current.next;
            
            // 如果该节点还有下一个节点，加入堆
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }
        
        return dummy.next;
    }
}

代码说明 #

1. 优先队列初始化：使用Lambda表达式定义比较器，确保堆顶始终是val最小的节点。
2. 初始化堆：遍历所有链表，将非空的头节点加入堆中。
3. 合并过程：每次取出堆顶的最小节点，接到结果链表的尾部，然后将该节点的next节点（如果存在）加入堆，重复直到堆为空。
4. 哑节点（dummy）：用哑节点简化结果链表的头节点处理，避免判断结果链表是否为空的冗余逻辑。

内容的提问来源于stack exchange，提问作者Aswinkumar S