# Merge K Sorted Lists

This page explains Java solution to problem `Merge K Sorted Lists` using `Priority Queue` data structure.

## Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Example 2:

Input: lists = [[]]
Output: []

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

/**
* 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 MergeKSortedLists {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;

PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
public int compare(ListNode l1, ListNode l2) {
return Integer.compare(l1.val, l2.val);
}
});

for(ListNode list: lists) {
if(list != null)
pq.offer(list);
}

ListNode dummy = new ListNode(-1);
ListNode head = dummy;
while(!pq.isEmpty()) {
ListNode node = pq.poll();
dummy.next = node;
dummy = dummy.next;
if(node.next != null)
pq.offer(node.next);
}