23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:

[
  1->4->5,
  1->3->4,
  2->6
]

Output:

 1->1->2->3->4->4->5->6


Thoughts:

This is my accepted but not really efficient solution. (in the last 10% in CPU time and Mem Usage)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode cur = new ListNode(0);
        ListNode result = cur;
        while(!isAllEmpty(lists)){

            int min = Integer.MAX_VALUE;
            int min_index = Integer.MAX_VALUE;
            int i = -1;
            for(ListNode l : lists){
                i ++;
                if (l == null){
                    continue;
                }
                if(l.val < min){
                    min = l.val;
                    min_index = i;
                }
                
            }
           
            cur.next = lists[min_index];
            cur = cur.next;
            lists[min_index] = lists[min_index].next;
        }
        
        return result.next;
    }
    
    
    public boolean isAllEmpty(ListNode[] ln){
        for(ListNode l : ln){
            if(l != null){
                return false;
            }
        }
        return true;
    }
}

 

 


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.