# 0023. Merge k Sorted Lists

<https://leetcode.com/problems/merge-k-sorted-lists>

## Description

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

*Merge all the linked-lists into one sorted linked-list and return it.*

**Example 1:**

```
**Input:** lists = [[1,4,5],[1,3,4],[2,6]]
**Output:** [1,1,2,3,4,4,5,6]
**Explanation:** The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```

**Example 2:**

```
**Input:** lists = []
**Output:** []
```

**Example 3:**

```
**Input:** lists = [[]]
**Output:** []
```

**Constraints:**

* `k == lists.length`
* `0 <= k <= 10^4`
* `0 <= lists[i].length <= 500`
* `-10^4 <= lists[i][j] <= 10^4`
* `lists[i]` is sorted in **ascending order**.
* The sum of `lists[i].length` won't exceed `10^4`.

## ac1: heap sort

O(Nlogk): N is the total amount of nodes, k is the length of lists

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // build priority heap
        // always take lists[0]
        // if lists[0] == null, swap to tail, reduce 1 loop
        // heapify(list[0])

        // corner cases
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];

        // build binary heap
        for (int i = lists.length - 1; i >= 0; i--) {
            heapify(lists, i);
        }

        // dummy node take result;
        ListNode dummy = new ListNode(0);
        ListNode d = dummy;

        // loop
        for (int k = lists.length-1; k > 0; k--) {
            while (lists[0] != null) {
                heapify(lists, 0);
                d.next = lists[0];
                d = d.next;
                lists[0] = lists[0].next;
            }
            ListNode tmp = lists[k];
            lists[k] = lists[0];
            lists[0] = tmp;
        }
        d.next = lists[0];

        return dummy.next;
    }
    private void heapify(ListNode[] lists, int i) {
        int min = i, l = 2*i+1, r = 2*i+2, n = lists.length;

        // compare root & left;
        if (l < n && lists[l] != null) {
            if (lists[min] == null || lists[l].val < lists[min].val) {
                min = l;
            }
        }

        // compare right & min
        if (r < n && lists[r] != null) {
            if (lists[min] == null || lists[r].val < lists[min].val) {
                min = r;
            }
        }

        // swap?
        if (min == i || lists[min] == null) {
            return; // already min, no need to swap.
        } else {

        // swap root & minIdx
            ListNode tmp = lists[i];
            lists[i] = lists[min];
            lists[min] = tmp;
        }

        // heapify minIdx
        heapify(lists, min);
    }
}
```

## AC2: priority queue

<https://leetcode.com/problems/merge-k-sorted-lists/discuss/10528/A-java-solution-based-on-Priority-Queue>

```
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode r = dummy;

        // PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> {return a.val - b.val;});
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        for (ListNode n : lists) {
            if (n != null) pq.offer(n);
        }

        while (pq.size() > 1) {
            ListNode curr = pq.poll();
            r.next = curr;
            r = r.next;
            if (curr.next != null) pq.offer(curr.next);
        }

        if (pq.size() == 1) {
            r.next = pq.poll();
        }

        return dummy.next;
    }
}
```

## other solutions

* divide & conquer, O(Nlogk)


---

# 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://jaywin.gitbook.io/leetcode/solutions/0023-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.