Formatted question description: https://leetcode.ca/all/23.html

# 23 - Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ]

Output: 1->1->2->3->4->4->5->6

### MergeSort solution

The first thing that comes to mind is the two-by-two merger, that is, the first two are merged first, and then the third is merged, and then the fourth to the kth. This kind of thinking is correct, but it is not efficient and cannot pass OJ, so we can only change the way of thinking. Divide and Conquer Approach are needed here.

Simply, it is divided into half and half, for example, k linked lists are first divided into the task of merging two `k/2`

linked lists, and then continuously divided down, until they are divided into tasks with only one or two linked lists, and start to merge.

For example, if you merge 6 linked lists, then according to the divide and conquer method, first merge 0 and 3, 1 and 4, and 2 and 5 respectively. So next time you only need to merge 3 linked lists, then merge 1 and 3, and finally merge with 2.

The k in the code is calculated by `(n+1)/2`

, why add 1 here?

- This is for when n is odd, k can always start from the second half,
- for example, when n=5, then at this time k=3, then 0 and 3 are merged, 1 and 4 are merged, and the middle 2 is vacant.
- When n is an even number, adding 1 will not have any effect. For example, when n=4 and k=2, then 0 and 2 are combined, and 1 and 3 are combined, which perfectly solves the problem.

##### big-o analysis

time-complex `O(N*logK)`

`N`

is the total number of nodes-
`k`

is the number of linked lists.`public ListNode merge(ListNode[] lists, int start, int end) { int mid = (end - start) / 2 + start; ListNode leftHalf = merge(lists, start, mid); ListNode rightHalf = merge(lists, mid + 1, end);`

Reference: https://leetcode.com/problems/merge-k-sorted-lists/solution/

- We can merge two sorted linked list in
`O(n)`

time where n is the total number of nodes in two lists. - Sum up the merge process and we can get: sum all nodes
`logk`

times (height of tree) =>`O(Nlogk)`

### Heap solution

Put the smallest node of each list into a priority queue (min heap). Every time a node is removed from the queue, the node is inserted into the next node in its list, And so on until all nodes have passed the priority queue.

Since the size of the priority queue is always k, and the complexity of each insertion is log k, a total of nk nodes have been inserted.

Heap solution: heap.offer(polled.next); Here, the offer() parameter of heap cannot be null, because polled is not null before updating currentNode

```
if (polled.next != null) {
heap.offer(polled.next); // @note: offer()参数不能是null
}
```

The time complexity is `O(n * k * logk)`

, and the space complexity is `O(k)`

.