Simple Recursive Approach


  • 0
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public ListNode min(ListNode nodeOne, ListNode nodeTwo){
            
            return (nodeOne != null && nodeTwo != null)? ((nodeOne.val <= nodeTwo.val)? nodeOne : nodeTwo) : ((nodeOne != null)? nodeOne : nodeTwo);
        }
        
        public ListNode merge(ListNode nodeOne, ListNode nodeTwo){
            
            ListNode dummy = new ListNode(-1);
            ListNode pointer = dummy;
            
            while ( nodeOne != null || nodeTwo != null ) {
                
                ListNode minNode = min(nodeOne,nodeTwo); 
                
                pointer.next = minNode;
                pointer = pointer.next;
            
                if ( nodeOne != null && nodeOne.val == minNode.val ) {
                
                    nodeOne = nodeOne.next;
                
                }else if ( nodeTwo != null ){
                
                    nodeTwo = nodeTwo.next;
                }
            }
            return dummy.next;
        }
        public ListNode mergeKLists(ListNode[] lists, int start, int end) {
               
               if ( end < start ) {
                   return null;
               }
               
               if ( start == end ) {
                   return lists[start];
               }
               
               if ( end - start == 1) {
                   return merge(lists[start],lists[end]);
               }
               
               int mid = start + (end-start)/2 ;
               
               ListNode left = mergeKLists(lists,start,mid);
               ListNode right = mergeKLists(lists,mid+1,end);
               
               return merge(left,right);
        }
        
        public ListNode mergeKLists(ListNode[] lists) {
            return mergeKLists(lists,0,lists.length-1);       
        }
    }
    

    using merge sort approach !


Log in to reply
 

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