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

## Solution

`Java Program Implementation`
```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {

if(lists == null || lists.length == 0)
return null;

PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length,new SortingComparator());

for(ListNode node : lists)
{
if(node != null)
}

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

while(!queue.isEmpty())
{
tail.next = queue.poll();
tail = tail.next;

if(tail.next != null)
}
return dummy.next;
}
}
class SortingComparator implements Comparator<ListNode>{
public int compare(ListNode node1,ListNode node2)
{
if(node1.val < node2.val)
return -1;
else if(node1.val == node2.val)
return 0;
else
return 1;
}
}
```