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.

&nbsp;
Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1-&gt;4-&gt;5,
  1-&gt;3-&gt;4,
  2-&gt;6
]
merging them into one sorted list:
1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4-&gt;5-&gt;6


Example 2:

Input: lists = []
Output: []


Example 3:

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


&nbsp;
Constraints:


	k == lists.length
	0 &lt;= k &lt;= 104
	0 &lt;= lists[i].length &lt;= 500
	-104 &lt;= lists[i][j] &lt;= 104
	lists[i] is sorted in ascending order.
	The sum of lists[i].length will not exceed 104.


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from heapq import heappush,heappop
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        heapq.heapify(heap)
        start = end = ListNode(-1)
        for i in lists:
            if i:
                heappush(heap,(i.val,id(i),i))
        while heap:
            val,iD,node = heappop(heap)
            end.next = node
            node = node.next
            end = end.next
            if node:
                heappush(heap,(node.val,id(node),node))
                
        return start.next
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
    if(lists == null || lists.length < 1) return null;

     //add the first chunk of linkedlist to res,
     //so later we started from index 1
    ListNode res = lists[0];

    //traverse the lists and start merge by calling mergeTwo
    for(int i = 1; i < lists.length; i++){
        res = mergeTwo(res, lists[i]);
    }

    return res;
}
    //leetcode 21 technics
    private ListNode mergeTwo(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        if(l1.val < l2.val){
            l1.next = mergeTwo(l1.next, l2);
            return l1;
        } else{
            l2.next = mergeTwo(l2.next, l1);
            return l2;
        }
    }
}
class Solution {
public:
    struct compare
    {
        bool operator()(ListNode* &a,ListNode* &b)
        {
            return a->val>b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,compare>minh;
        for(int i=0;i<lists.size();i++)
        {
           if(lists[i]!=NULL) minh.push(lists[i]);
        }
        ListNode* head=new ListNode(0);
        ListNode* temp=head;
        while(minh.size()>0)
        {
            ListNode* p=minh.top();
            minh.pop();
            temp->next=new ListNode(p->val);
            temp=temp->next;
            if(p->next!=NULL) minh.push(p->next);
        }
        return head->next;
    }
};
var mergeKLists = function(lists) {    
    // Use min heap to keep track of the smallest node in constant time.
    // Enqueue and dequeue will be log(k) where k is the # of lists
    // b/c we only need to keep track of the next node for each list
    // at any given time.
    const minHeap = new MinPriorityQueue({ priority: item => item.val });
    
    for (let head of lists) {
        if (head) minHeap.enqueue(head);
    }
    
    // Create tempHead that we initiate the new list with
    // Final list will start at tempHead.next
    const tempHead = new ListNode();
    let curr = tempHead;
    
    while (!minHeap.isEmpty()) {
        const { val, next } = minHeap.dequeue().element;
        curr.next = new ListNode(val);
        curr = curr.next;
        
        if (next) minHeap.enqueue(next);
    }
    
    return tempHead.next;
};
Merge k Sorted Lists