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

public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ListNode fakeHead = new ListNode(-1);
        ListNode runner = fakeHead;
        int nonTraversed = 0;
        //count the number of not-null ListNode
        for(ListNode curr:lists){
            if(curr!=null){
                nonTraversed++;
            }
        }
        while(nonTraversed>0){
            int min = Integer.MAX_VALUE;
            int minIndex = -1;
            for(int i=0;i<lists.size();i++){
                ListNode curr = lists.get(i);
                if(curr!=null){
                    if(curr.val<min){
                        minIndex = i;
                        min = curr.val;
                    }
                }
            }
            runner.next = lists.get(minIndex);
            runner = runner.next;
            lists.set(minIndex, lists.get(minIndex).next);
            if(lists.get(minIndex)==null){
                nonTraversed--;
            }
        }
        return fakeHead.next;
    }

O(N*k) k is the size of lists and N is the total number of elements in all the inputs lists

We can improve our solution by using Heap which can have O(Nlogk) runtime complexity.

Share