Java Solution without recursion (Feel free to comment)


  • 0
    B
    public class Solution {
    
     public ListNode mergeKLists(List<ListNode> lists) {
    
         //Base case where list size is 0 or 1
          if(lists.size() == 0){
              return null;
          }
          if(lists.size() == 1){
        	  ListNode l = lists.get(0);
              return lists.get(0);
          }
          
          while(lists.size() > 1){
        	  int size = lists.size();
        	  ArrayList<Integer> remove_index = new ArrayList<Integer>();
    
              //Compare a pair of lists at a time and merge into a single list and remove the 2nd list of the pair
              for(int i = 0; i < size-1; i= i+2){
              ListNode l1 = lists.get(i);
              ListNode l2 = lists.get(i+1);
              lists.set(i, merge(l1,l2));
              remove_index.add(i+1);
              }
    
              //Remove lists that have already been compared, starting from the larger index so it wont have index issues
              for(int i=remove_index.size()-1; i >= 0; i--){
            	  int r = remove_index.get(i);
            	  lists.remove(r);
              }
            }
    
        //Finally only 1 sorted list is left and returns that list
          return lists.get(0);
      }
      
      //Merge the 2 input lists
    
      public ListNode merge(ListNode l1, ListNode l2){
    
    	  if(l1 == null){
    		  return l2;
    	  }
    	  if(l2 == null){
    		  return l1;
    	  }
          ListNode result = new ListNode(0);
          ListNode head = result; 
          
          //Pick the smaller value and append to the result list 
          while(l1 != null && l2 != null){
              if(l1.val <= l2.val){
                  result.next = l1;
                  result = result.next;
                  l1 = l1.next;
              }
              else{
                  result.next = l2;
                  result = result.next;
                  l2 = l2.next; 
              }
              
          }
          if(l1 != null){
              result.next = l1; 
          }
          if(l2 != null){
              result.next = l2;
          }
          head = head.next;
          return head;
      }
    }

Log in to reply
 

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