23 Merge k Sorted Lists

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

My approach with this problem was to basically create a new linkedlist from scratch. I first grab all the min elements from the list. This will take O(k) time for k lists. Next, I find the minimum element according to that list. This will take O(N) for N minimum elements. That index is returned, and I insert it to the end of a linkedlist. This operation will take O(N) as well for N inserts. Next, I remove the head of the current minimum List. This will allow the next iteration to chose the next minimum element. Remove all will also take O(N) time.

Implementation 1

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


int findMinIndex(vector<int> &mins) {
    int min = mins.at(0);
    int index = 0;
    for (int i = 0; i < mins.size(); i++) {
        if (i < min) {
            min = mins.at(i);
            index = i;
        }    
    }

    return index;
}

void removeHead(ListNode *head) {
    // empty
    if (head == nullptr) return;

    ListNode *itr;
    itr = head;

    // deletions always occurs at head
    head = itr->next;
    delete itr;
}

void insert(ListNode *front, ListNode *end, ListNode *thisNode) {
    if (front == nullptr) {
        front = end = thisNode;
    }
    end->next = thisNode;
    end = thisNode;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    vector<int> mins(lists.size());
    ListNode *front, *end;
    front = end = nullptr;
    bool notEmpty = true;

    while (notEmpty) {
        // get all min elements given they are not empty
        for (int i = 0; i < lists.size() && (!lists.at(i)); i++) {
            mins.push_back(lists.at(i)->val);
            notEmpty = true;
        }
        // remove min_index
        int min_index = findMinIndex(mins);
        insert(front, end, lists.at(min_index));
        removeHead(lists.at(min_index));
        mins.clear();
        mins.resize(0);
        notEmpty = false;
    }

    return front;
}

Implementation 2

The Idea: Maintain a priority queue take keeps track of the minimum elements. Initially push all the front ListNode* into the pq. Then build a new list that continually takes the top of list pq (minimum element). As it does so, the minimum element replaces its position with the adjacent (next) element to it's list (if it's not null).

Time Complexity: O(nlogk) time, and O(K) space. The heap will only maintain k elements (the current minimum from each list). As soon as node is popped from the heap, it either becomes replaced by the next element in the list, or the list is empty, in which case no elements are added. Hence because the heap begins with at most k elements in the list, and at most one element is popped and replaced with a new element in the heap, the space complexity is proportional to the number of lists. For the time complexity, the heap does logk operations (since there are at most k elements in the heap) for all the elements in the lists combined (n).

struct CmpList
{
    bool operator()(const ListNode* lhs, const ListNode* rhs) const
    {
        return lhs->val > rhs->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, CmpList> pq;

    for (ListNode *lp : lists) 
        if (lp) pq.push(lp);


    ListNode *head = nullptr, *tail = nullptr;

    // get started by setting up head
    if (!pq.empty()) {
        ListNode *front = pq.top(); pq.pop();

        head = front;
        tail = head;

        if (front->next) pq.push(front->next);
    }

    while (!pq.empty()) {
        ListNode *front = pq.top(); pq.pop();

        tail->next = front;
        tail = front;

        if (front->next) pq.push(front->next);
    }

    if (tail) tail->next = nullptr;
    return head;
}

Testing

int main()
{
    ListNode* one = new ListNode(1);
    ListNode* two = new ListNode(2);
    ListNode* three = new ListNode(3);
    one->next = two;
    two->next = three;
    three->next = nullptr;

    vector<ListNode*> t1 = { one };
    ListNode *newHead1 = mergeKLists(t1);

    vector<ListNode*> t2 = { nullptr };
    ListNode *newHead2 = mergeKLists(t2);

}

Python

I aimed for a cleaner implementation here. We begin by iterating through the lists and appending the head nodes as tuple into a heapq. You may nice that our tuple carries an almost unnecessary 2 argument within the tuple. This argument is essentially used to break ties when two lists carry the same value. In our case, it does not matter which element gets added next to our list, but including the index i ensures when two lists are compared and they have the same value, a decision can be made in selecting which node to percolate in the heapq tree. In our case, we are arbitrary prioritizing the list that came first.

import heapq


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

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        Runtime O(nlogn) - where n is the number of elements
        Space O(k)
        """

        # initialize a dummy node for head start
        # it will do some of the work for us
        heap = []
        head = ListNode(0)
        tail = head

        # initialize the hq with the head of every list node
        # if it not empty hq with maintain smallest value
        # of the first tuple element by default
        for i in range(0, len(lists)):
            if lists[i]: heapq.heappush(heap, (lists[i].val, i, lists[i]))

        while heap:
            # point head to the next smallest element
            root = heapq.heappop(heap)
            tail.next = root[2]

            # iterate to the next node of the
            # linked list we popped from
            tail = tail.next

            # if that list isnt yet empty, then
            # store that next element into the hq
            if tail.next:
                heapq.heappush(heap, (tail.next.val, root[1], tail.next))

        # return head node which is after dummy node
        return head.next