Leetcode 23. Merge k Sorted Lists

3 solutions- Compare one by one & Heap &MergeSort

Solution 1- Compare one by one (slow)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head=new ListNode(0);
        if(lists.length==0){
            return head.next;
        }
        List<Integer> nums = new ArrayList<Integer>();
        
        ListNode p=head;
        for(int i=0;i<lists.length;i++){
            if(lists[i]!=null){
                nums.add(lists[i].val);}
            else{
                nums.add(Integer.MAX_VALUE);
            }
            
        }
        int minValue=Collections.min(nums);
        if(minValue==Integer.MAX_VALUE){
            return head.next;
        }
        while(minValue!=Integer.MAX_VALUE){
            int index=nums.indexOf(minValue);
            p.next=lists[index];
            if(lists[index].next==null){
                nums.set(index,Integer.MAX_VALUE);
            }
            else{
                lists[index]=lists[index].next;
                nums.set(index,lists[index].val);
            }
            p=p.next;
            minValue=Collections.min(nums);
        }
        return head.next;
    }
}

Solution 2 Heap (PriorityQueue)

heap: https://www.cnblogs.com/CarpenterLee/p/5488070.html

class Solution {
   
public ListNode mergeKLists(ListNode[] lists) {
		if (lists == null || lists.length == 0)
			return null;
		PriorityQueue<ListNode> min = new PriorityQueue<ListNode>(11, new Comparator<ListNode>() {
			public int compare(ListNode o1, ListNode o2) {
				return o1.val - o2.val;
			}
		});
		for (ListNode node : lists)
			if (node != null)
				min.offer(node);
		ListNode head = new ListNode(0);
		ListNode cur = head;
		while (!min.isEmpty()) {
			ListNode temp = min.poll();
			cur.next = temp;
			cur = cur.next;
			if (temp.next != null)
				min.offer(temp.next);
		}
		cur.next = null;
		return head.next;

}
}

Solution 3 MergeSort

class Solution {
   public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int begin = 0, end = lists.length - 1;
        while (begin < end) {
            int mid = (begin + end - 1) / 2;
            for (int i = 0; i <= mid; i++) {
                lists[i] = merge2list(lists[i], lists[end - i]);
            }
            end = (begin + end) / 2;
        }
        return lists[0];
    }
    public ListNode merge2list(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode dummy = new ListNode(-1), cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = l2;
                l2 = l2.next;
            }
        }
        if (l1 != null) cur.next = l1;
        if (l2 != null) cur.next = l2;
        return dummy.next;
    }
}

Thanks for the following references.
reference-Heap
reference-MergeSort
reference-Complexity Analysis