23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution

Approach 1: use a priority queue to keep the current heads -- O(N logk).

Approach 2: merge pairs of lists until there's 1 big list left -- O(N logk).

Code (Python)

Approach 1:

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # random.random() just to avoid comparing ListNodes
        heap = [(head.val, random.random(), head) for head in lists if head]
        heapq.heapify(heap)
        
        merged_head = ListNode(0)
        current = merged_head
        while heap:
            val, id, node = heapq.heappop(heap)
            current.next = node
            current = current.next
            if node.next:
                heapq.heappush(heap, (node.next.val, random.random(), node.next))
        
        current.next = None
        return merged_head.next

Approach 2:

    def mergeKLists(self, lists):
        if not lists:
            return None
        lists = collections.deque(lists)
        while len(lists) > 1:
            lists.append(self.merge2Lists(lists.popleft(), lists.popleft()))
        return lists[0]
    
    def merge2Lists(self, l1, l2):
        dummy = ListNode(0)
        current = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        if l1:
            current.next = l1
        else:
            current.next = l2
        return dummy.next

Code (C++)

Approach 1:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// Compare one by one.
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        vector<ListNode*> p(n, NULL);
        for (int i = 0; i < n; ++i)
        {
            if (lists[i])
                p[i] = lists[i];
        }
        ListNode dummyHead(0);
        ListNode *d = &dummyHead;
        while (true)
        {
            int minIdx = -1;
            for (int i = 0; i < lists.size(); ++i)
            {
                if (p[i] && (minIdx < 0 || p[minIdx]->val > p[i]->val))
                    minIdx = i;
            }
            if (minIdx < 0)
                break;
            d->next = p[minIdx];
            d = d->next;
            p[minIdx] = p[minIdx]->next;
        }
        return dummyHead.next;
    }
};

// Minimum heap.
class Solution {
private:
    struct cmp {
        bool operator() (ListNode *a, ListNode *b) {
            return a->val > b->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for (int i = 0; i < n; ++i)
        {
            if (lists[i])
                q.push(lists[i]);
        }
        ListNode dummyHead(0);
        ListNode *d = &dummyHead;
        while (!q.empty())
        {
            d->next = q.top();
            d = d->next;
            q.pop();
            if (d->next)
                q.push(d->next);
        }
        return dummyHead.next;
    }
};

Approach 2:

// Merge with divide and conquer.
class Solution {
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummyNode(0);
        ListNode *d = &dummyNode;
        while (l1 || l2)
        {
            if (l1 == NULL || l2 && l2->val <= l1->val)
            {
                d->next = l2;
                l2 = l2->next;
            }
            else
            {
                d->next = l1;
                l1 = l1->next;
            }
            d = d->next;
        }
        return dummyNode.next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (n == 0)
            return NULL;
        for (int interval = 1; interval < n; interval *= 2)
        {
            for (int i = 0; i < n && i + interval < n; i += interval * 2)
            {
                lists[i] = mergeTwoLists(lists[i], lists[i+interval]);
            }
        }
        return lists[0];
    }
};