# 23. Merge k Sorted Lists

用堆来实现弹出，一共只有k个元素，堆每次弹出最小的数的操作是 $$O(1)$$ ，堆每次删除和修改的操作需要 $$O(lgk)$$ ，这道题的时间复杂度是 $$O(nlgk)$$ 

{% tabs %}
{% tab title="Java(O(KN)" %}

```java
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int min_index = 0;
        ListNode dump = new ListNode();
        ListNode h = dump;
        while(true) {
            boolean isBreak = true;
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < lists.length; i ++) {
                if(lists[i] != null) {
                    if(lists[i].val < min) {
                        min_index = i;
                        min = lists[i].val;
                    }
                    isBreak = false;
                } 
            }
            if(isBreak)
                break;
            ListNode temp = new ListNode(lists[min_index].val);
            h.next = temp;
            h = h.next;
            lists[min_index] = lists[min_index].next;
        }
        h.next = null;
        return dump.next;
    }
}
```

{% endtab %}

{% tab title="Java(O(NlgK), priorityQueue)" %}

```java
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Comparator<ListNode> cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode n1, ListNode n2) {
                return n1.val - n2.val;
            }
        };
        
        Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
        for(ListNode l : lists) {
            if(l != null) {
                q.add(l);
            }
        }
        ListNode dump = new ListNode();
        ListNode p = dump;
        while(!q.isEmpty()) {
            p.next = q.poll();
            p = p.next;
            ListNode next = p.next;
            if(next != null)
                q.add(next);
        }
        return dump.next;
    }
}java
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/vi.-linked-list/23.-merge-k-sorted-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.