Is the complexity O(kn)?

Question

Here is my solution. Is it O(kn)? Do you guys have better solutions?

 /**
 * 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(ArrayList<ListNode> lists) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (lists == null) return null;
        if (lists.isEmpty()) return null;
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (lists.size() > 0) {
            int toRemove = -1;
            int emptyCount = 0;
            for (int i = 0; i < lists.size(); i++) {
                if (lists.get(i) != null) {
                    if (toRemove == -1) toRemove = i;
                    else {
                        if (lists.get(i).val < lists.get(toRemove).val) {
                            toRemove = i;
                        }
                    }
                } else {
                    emptyCount++;
                }
            }
            if (emptyCount == lists.size()) break;
            ListNode toDelete = lists.remove(toRemove);
            tail.next = toDelete;
            tail = tail.next;
            lists.add(toDelete.next);
        }
        tail.next = null;
        return head.next;
    }
}

Comments

Hi Ynisgol, welcome! Could you spend some time explaining your approach, so that the community understand which part of your solution that could be improve?

---

i know it's O(n) time complexity for k=2, so O(kn) should be correct. Space is O(1) if u r merging to one of the original lists.

You can surely do O(nlogk) if you do something like merge sort. Eg. for k=4, merge l2 to l1, l4 to l3, then l3 to l1.

---

Thanks zchen! Seems you provide an answer for this question, not just a comment. Could you please paste your content and post it as answer?

Answer 1

My idea is based on merge 2 sorted list. If we merge every adjacent 2 lists per iteration, we needs log2(k) iterations, where merge 2 sorted list costs O(n) per iteration. Thus the run time is O(log(k)n).

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(lists.isEmpty()) return null;
        if(lists.size() == 1) return lists.get(0);
        int k = lists.size();
        int log = (int)(Math.log(k)/Math.log(2));
        log = log < Math.log(k)/Math.log(2)? log+1:log; // take ceiling
        for(int i = 1; i <= log; i++){
            for(int j = 0; j < lists.size(); j=j+(int)Math.pow(2,i)){
                int offset = j+(int)Math.pow(2,i-1);
                lists.set(j, mergeTwoLists(lists.get(j), (offset >= lists.size()? null : lists.get(offset))));
            }
        }
        return lists.get(0);
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head = l1.val > l2.val? l2:l1;
        if(head.equals(l2)){
            l2 = l1;
            l1 = head;
        }
        while(l1.next != null && l2 != null){
            if(l1.next.val > l2.val){
                ListNode tmp = l1.next;
                l1.next = l2;
                l2 = l2.next;
                l1 = l1.next;
                l1.next = tmp;
            }
            else
                l1 = l1.next;
        }
        if(l2 != null){
            l1.next = l2;
        }
        return head;
    }
}