My simple java Solution use recursion


  • 85
    M
    public static ListNode mergeKLists(ListNode[] lists){
        return partion(lists,0,lists.length-1);
    }
    
    public static ListNode partion(ListNode[] lists,int s,int e){
        if(s==e)  return lists[s];
        if(s<e){
            int q=(s+e)/2;
            ListNode l1=partion(lists,s,q);
            ListNode l2=partion(lists,q+1,e);
            return merge(l1,l2);
        }else
            return null;
    }
    
    //This function is from Merge Two Sorted Lists.
    public static ListNode merge(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val){
            l1.next=merge(l1.next,l2);
            return l1;
        }else{
            l2.next=merge(l1,l2.next);
            return l2;
        }
    }

  • 9
    Y

    to avoid integer overflow, use q = s + (e -s) / 2 instead


  • 1
    S

    Thanks for the excellent solution


  • 0
    J

    is the time complexity?


  • 0
    M

    It is O(nlgn).


  • 8
    M

    nlogk where k is the number of lists and n is total number of nodes.


  • 0
    O

    @yanggao, no need. s,q are indexes


  • 9
    O

    I did the same implementation as you. This is 3ms beating 93%

    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            return mL(lists, 0, lists.length - 1);
        }
        
        private ListNode mL(ListNode[] lists, int l, int r) {
            if (r < l) return null;
            if (r == l) return lists[r];
            
            int mid = (l + r) / 2;
            ListNode a = mL(lists, l, mid), b = mL(lists, mid + 1, r);
            ListNode dmHead = new ListNode(0), cur = dmHead;
            while (a != null && b != null) {
                if (a.val < b.val) {
                    cur.next = a;
                    a = a.next;
                } else {
                    cur.next = b;
                    b = b.next;
                }
                cur = cur.next;
            }
            cur.next = (a != null) ? a : b;
            
            return dmHead.next;
        }
    }

  • 1
    D

    good answer. reminds me of merge sort


  • 4
    J

    The complexity is O(nk), it's not O(nlogk). Stop saying it's O(nLogK) please.
    This is same as following:
    get two listNodes -> merge them -> put merged result into original list.
    It consumes one List node every time until it only has one ListNode


  • 8
    C

    No, it is O(nlogk), merge takes O(n) time and partition takes O(logk) time


  • 0
    N

    @spritmouselet
    you are wrong ! it should be O(nlogk), becasue we mergered k sorted lists. so we do need merge them from one length lists.


  • 2
    D

    can anyone tell me why this solution is faster than priorityqueue?


  • 1
    S

    @daiqiang1117
    The complexity for priority queue and this method is same i.e. nlogk. Because in priority queue you will make some n additions ( assuming n nodes ) for a list length of k.


  • 1
    D

    @shilpa6
    Now I think the answer is quite clear. Use PQ, both poll and offer are logK operations.
    So PQ solution comes out (n * 2 * logK)
    However divide conquer is (n * logk)


  • 0
    F

    Isn't the time complexity o(nklogn) where k is avg length of linked list??


  • 0
    L

    @fiona8957 said in My simple java Solution use recursion:

    Isn't the time complexity o(nklogn) where k is avg length of linked list??


  • 0
    M

    Yes. The complexity of this algorithm is o(nklogn)


  • 0
    M

    Sorry. The complexity is O(nklogk).


  • 6
    J

    @Manojbattula Some people say this recursion method is O(nlogk), while others say O(nklogk)I think it depends the how you define your n. In a previous answer, it is defined as TOTAL number of nodes, which already considering k...So I think all of you are correct.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.