23. Merge k Sorted Lists - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        queue = []
        for head in lists:
            if head:
                heapq.heappush(queue, (head.val, id(head), head)) # pq looks at the next value in the tuple (in this case, id), and sort based on that value. Suppose there is no id and there is tie in terms of first element in tuple, pq will try to compare the 3rd element ListNode, which is however not comparable. 
        
        mergedList = ListNode()
        cur = mergedList
        while queue:
            _, _, node = heapq.heappop(queue)
            cur.next = node
            cur = node
            if node.next:
                heapq.heappush(queue, (node.next.val, id(node.next), node.next)) 
                
        return mergedList.next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        
        mid = len(lists) // 2
        if mid == 0:
            return lists[0]
        
        left, right = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
        return self.merge2Lists(left, right)
    
    def merge2Lists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode()
        cur = head
        while list1 is not None and list2 is not None:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        
        if list1 is not None:
            cur.next = list1
        elif list2 is not None:
            cur.next = list2
        
        return head.next

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i]) {
                pq.push(lists[i]);
                lists[i] = lists[i]->next;
            }
        }
        
        ListNode dummy(0);
        ListNode* p = &dummy;
        while (! pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            if (node->next) pq.push(node->next);
            
            p->next = node;
            p = p->next;
        }
        return dummy.next;
    }
private:
    class Cmp {
    public:
        bool operator()(ListNode* node1, ListNode* node2) {
            return node1->val > node2->val;
        }
    };
};

(k/2) * 2n
k/2/2 * 4n
.
.
.
-------------
log k times, O(nk) for each time

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())  return nullptr;
        while (lists.size() > 1) {
            int sz = lists.size();
            for (int i = 0; i < sz / 2; i++) {
                lists[i] = merge2Lists(lists[i], lists.back());
                lists.pop_back();
            }
        }
        return lists[0];
    }
private:
    ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* p = &dummy;

        while (l1 && l2) {
            if (l1->val <= l2->val) {
                p->next = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        l1 ? p->next = l1 : p->next = l2;
        return dummy.next;
    }
};

T(K_list) = 2T(K/2_list) + O(NK)
	  = 4T(K/4_list) + 2O(NK/2) + O(Nk)
	  = ...
	  = logKT(1_list) + NKlogK
	  = NKlogK

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int k = lists.size();
        return k == 0 ? nullptr : helper(lists, 0, k - 1);
    }
private:
    ListNode* helper(vector<ListNode*>& lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        
        int mid = start + (end - start) / 2;
        ListNode* l1 = helper(lists, start, mid);
        ListNode* l2 = helper(lists, mid + 1, end);
        return merge2Lists(l1, l2);
    }

    ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* p = &dummy;

        while (l1 && l2) {
            if (l1->val <= l2->val) {
                p->next = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        l1 ? p->next = l1 : p->next = l2;
        return dummy.next;
    }
};