Leetcode 23: Merge K Sorted Lists

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

Notes:

A very classic question!

The basic idea is divide and conquer. After dividing, the basic task becomes merging two sorted lists, which is very easy to implement.

The time complexity is O(N*M), where N is the number of list and M is the averaged number of notes for each list. Since each note is processed only one time. (see the update below)

 In comparison, if we a used naive brute-force way to do this by two-layer for loops, the time complexity is O(N*N*M). Since we will repeat to process the notes that have already been temporally processed before.

[update in 2019-12-03] the time complexity of the following code is O(N*logN*M), which is derived from the typical divide and conquer algorithm (similar to merge sort).

See the code below:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return div(lists, 0, lists.size());
    }

private:
    ListNode* div(vector<ListNode*> &ls, int left, int right) {
        if(left == right) return NULL;
        if(left + 1 == right) return ls[left];
        int mid = left + (right - left)/2;
        return mergeSorted(div(ls, left, mid), div(ls, mid, right));
    }

    ListNode* mergeSorted(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy, *p1 = l1, *p2 = l2;
        while(p1 && p2) {
            if(p1->val <= p2->val) {
                p->next = p1;
                p1 = p1->next;
            }
            else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        if(p1) p->next = p1;
        else p->next = p2;
        return dummy->next;
    }
};