Cacher is the code snippet organizer for pro developers

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 
 // Time complexity: O(Nlogk)
 // Space complexity: O(1)
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //TODO: make sure that we are not passing empty lists to mergeLists
        
        //HANDLING EDGE CASES
        if(lists.length == 0)
            return null;
        
        if(lists.length == 1) //do we need this?
            return lists[0];
        
        int interval = 1;
        while(interval < lists.length) {
            int i = 0;
            while (i < lists.length) {
                if(i + interval < lists.length)
                    lists[i] = mergeList(lists[i], lists[i + interval]);
                i += interval * 2;
            } 
          interval *= 2;
        }
        
        return lists[0];
    }
    
    
    public ListNode mergeList(ListNode A, ListNode B) {
        
        ListNode dummy  = new ListNode(0);
        ListNode node = dummy;
        
        while(A != null && B != null) {
            if (A.val <= B.val) {
                node.next = A;
                A = A.next;
            } else {
               node.next = B;
               B = B.next;
            }
            node = node.next;
        }
        
        if (A != null) 
            node.next = A;
        
        
        if (B != null) 
            node.next = B;
         
        
        return dummy.next;
    }
}