Solution by awice


  • 1

    Approach #1: Brute Force [Accepted]

    Intuition and Algorithm

    Collect every value of every list and sort it, then create a new list with those sorted values.

    Java

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            List<Integer> values = new ArrayList();
            for (ListNode node : lists){
                while (node != null) {
                    values.add(node.val);
                    node = node.next;
                }
            }
    
            Collections.sort(values);
            ListNode ans = new ListNode(0);
            ListNode cur = ans;
            for (int v : values){
                cur.next = new ListNode(v);
                cur = cur.next;
            }
            return ans.next;
        }
    }
    

    Python

    class Solution(object):
        def mergeKLists(self, lists):
            values = []
            for node in lists:
                while node:
                    values.append(node.val)
                    node = node.next
    
            values.sort()
            ans = cur = ListNode(None)
            for v in values:
                cur.next = cur = ListNode(v)
            return ans.next
    

    Complexity Analysis

    • Time Complexity: $$O(V \log V)$$, where $$V$$ is the total number of values in all lists in lists. values will have length $$V$$ and take $$O(V \log V)$$ time to sort.

    • Space Complexity: $$O(V)$$, the length of values and ans.


    Approach #2: Sequential Merge [Time Limit Exceeded]

    Intuition and Algorithm

    Merge every list into our answer, one at a time.

    Java

    class Solution {
        public ListNode merge(ListNode A, ListNode B) {
            if (A == null) return B;
            if (B == null) return A;
            if (A.val < B.val) {
                A.next = merge(A.next, B);
                return A;
            } else {
                B.next = merge(A, B.next);
                return B;
            }
        }
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            ListNode ans = lists[0];
            for (int i = 1; i < lists.length; i++){
                ans = merge(ans, lists[i]);
            }
            return ans;
        }
    }
    

    Python

    class Solution(object):
        def mergeKLists(self, lists):
            def merge(A, B):
                ans = cur = ListNode(None)
                while A and B:
                    if A.val > B.val: A, B = B, A
                    cur.next = cur = ListNode(A.val)
                    A = A.next
                cur.next = A or B
                return ans.next
    
            if not lists: return []
            ans = reduce(merge, lists)
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(V * k)$$, where $$V$$ is the total number of values in all lists in lists, and $$k$$ is the length of lists. Every merge operation with lists of length $$A$$ and $$B$$ is $$O(A+B)$$. In the worst case, we might merge almost all $$V$$ of our elements $$k-1$$ times, for a total complexity of $$O(V * k)$$.

    • Space Complexity: $$O(V)$$, the length of ans.


    Approach #3: Divide And Conquer Merge [Accepted]

    Intuition and Algorithm

    Instead of merging the smallest lists together K-1 times, merge the largest lists together $$O(\log K)$$ times.

    To manage this task, we will let mergeInterval(..., s, e) be the result of merging the lists lists[s], lists[s+1], ..., lists[e] together. We will merge the lists in the left half of the interval, and the right half; then merge those two results together.

    Java

    class Solution {
        public ListNode merge(ListNode A, ListNode B) {
            // As in Approach #2
        }
        public ListNode mergeInterval(ListNode[] lists, int s, int e) {
            if (s == e) return lists[s];
            if (s > e) return null;
            int m = (s + e) / 2;
            ListNode left = mergeInterval(lists, s, m);
            ListNode right = mergeInterval(lists, m+1, e);
            return merge(left, right);
        }
        public ListNode mergeKLists(ListNode[] lists) {
            return mergeInterval(lists, 0, lists.length - 1);
        }
    }
    

    Python

    class Solution(object):
        def mergeKLists(self, lists):
            def merge(A, B):
                # As in Approach #2
    
            def merge_interval(s, e):
                if s == e: return lists[s]
                if s > e: return None
                m = (s + e) // 2
                left = merge_interval(s, m)
                right = merge_interval(m+1, e)
                return merge(left, right)
    
            return merge_interval(0, len(lists) - 1)
    

    Complexity Analysis

    • Time Complexity: $$O(V * \log k)$$, where $$V$$ is the total number of values in all lists in lists, and $$k$$ is the length of lists. $$O(\log k)$$ merges are made, and all $$V$$ values are merged that many times.

    • Space Complexity: $$O(V)$$. Every value is stored at most one time.


    Approach #4: Priority Queue [Accepted]

    Intuition and Algorithm

    When building our answer, the next element will be the minimum of all of our lists. A priority queue is an ideal data structure to manage repeated queries of the minimum of some changing collection.

    We maintain heap, a priority queue of the head nodes of our lists. Then, the top of the priority queue is always the next value to be added to our answer, and if the next node of that list is nonempty, we'll add it to our heap.

    Java

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
                Comparator.<ListNode> comparingInt(node -> node.val));
    
            ListNode ans = new ListNode(0), cur = ans;
            for (ListNode node : lists) {
                if (node != null) heap.offer(node);
            }
            while (!heap.isEmpty()) {
                cur.next = heap.poll();
                cur = cur.next;
                if (cur.next != null) heap.offer(cur.next);
            }
            return ans.next;
        }
    }
    

    Python

    class Solution(object):
        def mergeKLists(self, lists):
            heap = [(A.val, A) for A in lists if A]
            heapq.heapify(heap)
    
            cur = ans = ListNode(None)
            while heap:
                val, node = heapq.heappop(heap)
                cur.next = cur = ListNode(val)
                node = node.next
                if node:
                    heapq.heappush(heap, (node.val, node))
    
            return ans.next
    

    Complexity Analysis

    • Time Complexity: $$O(V * \log k)$$, where $$V$$ is the total number of values in all lists in lists, and $$k$$ is the length of lists. Every poll (pop) and offer (push) operation during one execution of the while block is $$O(\log k)$$, since the priority queue has size $$O(k)$$. We do $$O(V)$$ of these operations.

    • Space Complexity: $$O(k)$$: we only used $$O(k)$$ additional space in storing heap.


  • 0

    The number of lists is already called k by the problem, it's unnecessary and confusing to invent additional variable K. And multiplying the number of lists with the largest length is rather pessimistic and inaccurate. Why not use the total number of elements instead?


  • 0

    @StefanPochmann I chose (case insensitive) K precisely because k was already defined in the problem, and I've always used capital letters in the complexity analysis portion and wanted to be consistent. I think this is a style choice, and after reading your comment I thought about it for a long time.

    The other part of your comment, I chose N, K because I felt N, K was more straightforward than to justify steps involving V = the number of values, but in retrospect I was wrong here.

    In total, I think you are right on both counts and I have edited this article to express it in terms of V, k instead.


  • 1

    @awice Case insensitive variables? Barbaric. Were you brought up by Basic coders? :-P


  • 0

    @StefanPochmann Could you please make some comments about my solution article if you're interested in the solution of this problem? Click here to read and I'll appreciate any kind of your help!


Log in to reply
 

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