Merge K Sorted List

	Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode mergeKLists(ArrayList<ListNode> lists) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (lists==null||lists.isEmpty()){
	return null;
	}
	Comparator<ListNode> comparator =new Comparator<ListNode>(){
	public int compare (ListNode node1, ListNode node2){
	if (node1.val>node2.val) return 1;
	else if (node1.val<node2.val) return -1;
	else return 0;
	}
	};
	PriorityQueue<ListNode> heap=new PriorityQueue<ListNode>(lists.size(),comparator);
	for (ListNode i:lists){
	if (i!=null){
	heap.add(i);
	}
	}
	ListNode head=null;
	ListNode cur=null;
	while(!heap.isEmpty()){
	ListNode newNode=heap.poll();
	if (head==null){
	head=newNode;
	cur=newNode;
	if (cur.next!=null){
	heap.add(cur.next);
	}
	}
	else{
	cur.next=newNode;
	cur=newNode;
	if(cur.next!=null){
	heap.add(cur.next);
	}
	}
	}
	return head;
	}
	}

view raw Merge k Sorted Lists.java hosted with ❤ by GitHub