# 23. Merge k Sorted Lists (Hard)

https://leetcode.com/problems/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
```

## Solutions

### 1.

``````class Solution {

public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}

ListNode pointer;

// Get the total number of the nodes
int size = 0;
for (int i = 0; i < lists.length; i++) {
pointer = lists[i];
while (pointer != null) {
size += 1;
pointer = pointer.next;
}
}

ListNode dummy = new ListNode(0);
pointer = dummy;

while ((size--) > 0) {
int index = -1;
int min = Integer.MAX_VALUE;

// Walk through the heads of visited stored in lists and find out the minDelete value
// and corresponding index in the list
for (int i = 0; i < lists.length; i++) {
if (lists[i] == null) {
continue;
}

if (lists[i].val < min) {
min = lists[i].val;
index = i;
}
}

pointer.next = lists[index];
pointer = pointer.next;

// Move the header of lists[index] to the next
lists[index] = lists[index].next;

pointer.next = null;
}

return dummy.next;
}
}
``````

### 2.

``````class Solution {

// With the help of PriorityQueue, we just pump values into the queue and
// don't have to take the order issue into consideration.

public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}

// Used to keep the values in ascending order
Queue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

// insert into priority queue and the elements are sorted automatically
for (int i = 0; i < lists.length; i++) {
if (lists[i] == null) {
continue;
}

ListNode node = lists[i];
while (node != null) {
node = node.next;
}
}

ListNode dummy = new ListNode(0);
ListNode pointer = dummy;

// poll all the elements in order and append them to a linked list
while (queue.peek() != null) {
pointer.next = queue.poll();
pointer = pointer.next;
}

pointer.next = null;

return dummy.next;
}
}
``````