Leetcode: Merge k Sorted Lists

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

Divide and Conquer solution

We merge lists by pairs till we have only one list. The complexity is $O(n log(k))$.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size()==0)
            return null;
        while(lists.size()>1)
        {
            List<ListNode> nextLists = new ArrayList<ListNode>();
            for(int i=0; i< lists.size()-1; i+=2)
            {
                nextLists.add(mergeLists(lists.get(i),lists.get(i+1)));
            }
            if (lists.size()%2==1)
                nextLists.add(lists.get(lists.size()-1));
            lists = nextLists;
        }
        return lists.get(0);
    }
    
    private ListNode mergeLists(ListNode list1, ListNode list2)
    {
        ListNode dummy = new ListNode(0);
        ListNode list = dummy;
        while(list1!=null && list2!=null)
        {
            if(list1.val<list2.val)
            {
                list.next = list1;
                list1 = list1.next;
            }
            else
            {
                list.next = list2;
                list2 = list2.next;
            }
            list = list.next;
        }
        if (list1 == null)
            list.next = list2;
        else
            list.next = list1;
        return dummy.next;
    }
}