Merge k Sorted Lists

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


Solution: Basic linked list implementation question. Search all lists and find the smallest element and append it at the tail of a sorted result list.
Tips: use lists.set(index, head.next) to move the head pointer to the next.

public class Solution {
    public ListNode mergeKLists(ArrayList lists) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int n = lists.size();
        while(true){
            int empty_list = 0;
            int min_value = Integer.MAX_VALUE;
            int min_index = 0;
            for(int i = 0; i < n; i++){
                if(lists.get(i) == null) 
                    empty_list++;
                else if(lists.get(i).val < min_value){
                    min_value = lists.get(i).val;
                    min_index = i;
                }
            }
            if(empty_list == n)
                break;
            ListNode head = lists.get(min_index);
            tail.next = head;
            tail = head;
            lists.set(min_index, head.next);
        }
        return dummy.next;
    }
}