Simple Iterative Java Solution


  • 0
    O
    
        public ListNode mergeKLists(ListNode[] lists) {
            if(null == lists || lists.length == 0 ){
                return null;
            }
            
            if(lists.length == 1){
                return lists[0];
            }
            
            
            int last = lists.length - 1;
            
            while(last != 0){
                int i = 0;
                int j = last;
                
                while(i < j){
                    lists[i] = merge(lists[i], lists[j]);
                    i++;
                    j--;
                    if(i >= j){
                        last = j;
                    }
                }
            }
            
            
            return lists[0];
            
        }
        
        private ListNode merge(ListNode l1, ListNode l2){
            if(null == l1 && null == l2){
                return null;
            }else if(null != l1 && null == l2){
                return l1;
            }else if(null == l1 && null != l2){
                return l2;
            }
            
            ListNode c1 = l1;
            ListNode c2 = l2;
            
            ListNode cur = new ListNode(0);
            ListNode dummy = cur;
            
            while(null != c1 && null != c2){
                if(c1.val < c2.val){
                    dummy.next = c1;
                    c1 = c1.next;
                }else{
                    dummy.next = c2;
                    c2 = c2.next;
                }                            
                dummy = dummy.next;
            }
            
            if(null != c1){
                dummy.next = c1;
            }
            
            if(null != c2){
                dummy.next = c2;
            }
            
            return cur.next;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.