/**
 * 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.length == 0 || lists == null){
            return null;
        }
        ListNode p = new ListNode();
        ListNode res = p;
        ArrayList<Integer> list = new ArrayList();
        int i = 0;
        ListNode s = lists[0];
        while(i < lists.length){
            while(s == null && (i+1) < lists.length){
                s = lists[++i];
            }
            if(s != null){
                list.add(s.val);
                s = s.next;
            }else{
                break;
            }
        }
        Collections.sort(list);
        int j = 0;
        if(list.size() == 0){
            return null;
        }
        while(j < list.size()){
            p.val = list.get(j);
            if(j != list.size() - 1){
                p.next = new ListNode();
                p = p.next;
            }
            j++;
            
        }
        return res;
    }
}