Leetcode 23: Merge k sorted lists

https://leetcode.com/problems/merge-k-sorted-lists/

 

Code 1:

import heapq
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        cur = dummy
        if not lists:
            return None

        h = [(lists[i].val, lists[i]) for i in xrange(len(lists)) if lists[i] ]

        heapq.heapify(h)

        while len(h) > 0:
            t = heapq.heappop(h)
            cur.next = t[1]
            cur = cur.next
            if t[1].next:
                heapq.heappush(h, (t[1].next.val, t[1].next)) 

        return dummy.next

Use a min-heap to store k lists’ heads. Build a heap requires O(k) time. Every time you pop the least value from the heap, and push into that value’s next node into the heap. Since there are N elements in total and each heap push takes O(logK) time, the algorithm takes O(K+NlogK) time (O(K) is for heapify) but also O(K) additional space.

See [1] and [2] why the time complexity of heapify is O(K).

[1] http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

[2] https://www.cs.bgu.ac.il/~ds122/wiki.files/Presentation09.pdf

 

Code 2:

Use O(NlogK) time and there is no additional space required. Everytime you merge k/2 pairs lists. Reference: https://leetcode.com/discuss/20774/sharing-straightforward-solution-without-structure-vector

class Solution {
public:
    ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (NULL == l1) return l2;
        else if (NULL == l2) return l1;
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty()) return NULL;
        int len = lists.size();
        while (len > 1) {
            for (int i = 0; i < len / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
            }
            len = (len + 1) / 2;
        }

        return lists.front();
    }
};

Similar Idea using Java:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head=null;
        ListNode former=null;
        while (l1!=null&&l2!=null) {
            if (l1.val>l2.val) {
                if (former==null) former=l2; else former.next=l2;
                if (head==null) head=former; else former=former.next;
                l2=l2.next;
            } else {
                if (former==null) former=l1; else former.next=l1;
                if (head==null) head=former; else former=former.next;
                l1=l1.next;
            }
        }
        if (l2!=null) l1=l2;
        former.next=l1;
        return head;

    }

    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size()==0) return null;
        if (lists.size()==1) return lists.get(0);
        if (lists.size()==2) return mergeTwoLists(lists.get(0), lists.get(1));
        return mergeTwoLists(mergeKLists(lists.subList(0, lists.size()/2)), 
            mergeKLists(lists.subList(lists.size()/2, lists.size())));
    }
}

https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue

 

Reference: