# Merge k Sorted Lists (H)

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
```

meaning of the title

The k ordered lists are merged into an ordered list.

thinking

Similar to the two-way merge method, the priority queue can be used to find the smallest of k nodes.

It is also possible to divide all linked lists into several groups and merge them into two routes at a time, and finally merge them into a large list.

The time complexity of the two methods is O(Nlogk)O(Nlogk)O(Nlogk), but the running time is quite different after actual submission. The reason may be that in the priority queue method, each node needs to be connected to a new list separately. In the divide-and-conquer method, when one of the two lists is null, the remaining nodes in the other list can be connected directly to the new list and omitted. Part of the time.

Code Implementation - Priority Queue

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(((o1, o2) -> o1.val - o2.val));
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
pq.offer(lists[i]);
}
}
while (!pq.isEmpty()) {
pointer.next = pq.poll();
pointer = pointer.next;
if (pointer.next != null) {
pq.offer(pointer.next);
}
}
}
}
```

Code implementation-divide and conquer

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// Exclude special cases first, otherwise array subscripts will overflow
if (lists.length == 0) {
return null;
}
for (int step = 1; step < lists.length; step *= 2) {
for (int i = 0; i + step < lists.length; i += 2 * step) {
lists[i] = mergeTwo(lists[i], lists[i + step]);
}
}
return lists;
}

private ListNode mergeTwo(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
pointer.next = l1;
l1 = l1.next;
} else {
pointer.next = l2;
l2 = l2.next;
}
pointer = pointer.next;
}
pointer.next = l1 == null ? l2 : l1;