# Merge k Sorted Lists

## Problem

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

## Example

Given lists:

[
2->4->null,
null,
-1->null
],

return -1->2->4->null.

## Code - Java

/**
* Definition for ListNode.
* public class ListNode {
*   int val;
*   ListNode next;
*   ListNode(int val) {
*     this.val = val;
*     this.next = null;
*   }
* }
*/
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {

if (lists == null || lists.size() == 0) {
return null;
}
Queue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), cmp);

ListNode head = new ListNode(0);
ListNode p = head;

for (ListNode node : lists) {
if (node != null) {
queue.offer(node);
}
}

while (!queue.isEmpty()) {
ListNode n = queue.poll();
p.next = n;
p = p.next;
if (n.next != null) {
queue.offer(n.next);
}
}

return head.next;
}

public Comparator<ListNode> cmp = new Comparator<ListNode>() {
@Override
public int compare(ListNode a, ListNode b) {
return a.val - b.val;
}
};
}