Two ways. One is minHeap, the other is mergeSort way(recursion, faster)


  • 2
    D

    minHeap: time - O(nlog(k)), space - O(k), n is total number of all the listnode, k is the length of lists

     public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            return heap(lists);
        }
        private ListNode heap(ListNode[] lists) {
            PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
                public int compare(ListNode a, ListNode b) {
                    return a.val - b.val;
                }
            });
            for (ListNode head : lists) {
                if (head != null)
                    pq.offer(head);
            }
            ListNode res = new ListNode(0);
            ListNode resHead = res;
            while (!pq.isEmpty()) {
                ListNode cur = pq.poll();
                res.next = cur;
                res = res.next;
                if (cur.next != null) {
                    pq.offer(cur.next);
                }
            }
            return resHead.next;
        }
    

    like mergeSort(recursion): time-O(vlog(k)), space- O(log(k)), v is average length of a list, k is length of lists.

     public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            return helper(lists, 0, lists.length - 1);
        }
        private ListNode helper(ListNode[] lists, int start, int end) {
                if (start == end) {
                    return lists[start];
                }
                int mid = (start + end) / 2;
                ListNode left = helper(lists, start, mid);
                ListNode right = helper(lists, mid + 1, end);
                return mergeTwo(left, right);
        }
        private ListNode mergeTwo(ListNode left, ListNode right) {
            ListNode head = new ListNode(0);
            ListNode newHead = head;
            while (left != null && right != null) {
                if (left.val  <= right.val) {
                    head.next = left;
                    left = left.next;
                } else {
                    head.next = right;
                    right = right.next;
                }
                head = head.next;
            }
            if (left != null) {
                head.next = left;
            }
            if (right != null) {
                head.next = right;
            }
            return newHead.next;
        }
    

  • 0
    A

    @daniel123 No really. For the divide & conquer merge, after every loop, although the number of listnode is halved, the average length of each listnode is doubled. So it is still O(nklog(k)), n being the original average length.


  • 1
    K

    @ayuanx There are log(k) levels. On each level, there are always N nodes in total. So the complexity is O(Nlog(k));


  • 0
    A

    @kotomi_null Think again. Every two N nodes merged together, you get 2*N nodes. So every level up, the number of nodes in each list doubles.


  • 1
    K

    @ayuanx Let me rephrase, N is the total number of all nodes, not the average length of a list. Let say list A has 20 nodes and, B 10, C 20, D 10. N = 60 here. We merge A and B, C and D at bottom level. There will be (10 + 20) + (10 + 20) = 60 = N ops on this level. Then we merge A-B and C-D (each list has 30 nodes now). There are still 30 + 30 = N ops.

    Is that clear now? If not, you could draw a tree and count ops yourself. Thanks


  • 0
    A

    @kotomi_null Then we are talking about the same thing.
    The symbols I use are:
    n: average length of each list.
    k: number of lists.
    So the total number of nodes == n*k, which is actaully your N.


Log in to reply
 

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