Merge k Sorted Lists

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

Iterative Solution:

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<ListNode *> sol;
        if (lists.size() == 0)
            return NULL;

        while (lists.size() - 1) {
            mergeTwo(lists[0], lists[1]);
            lists.erase(lists.begin() + 1);
        }
        return lists[0];
    }
  
    void mergeTwo(ListNode* &first, ListNode* &second) {
        ListNode *temp=NULL, *temp2=NULL, *prev=NULL, *iter = first;

        if (first == NULL) {
            first = second;
            return;
        }
        while(second!=NULL) {
            if (iter->val > second->val) {
                if (prev != NULL) {
                    // Insert into first, but not in beginning
                    temp2=second->next;
                    prev->next = second;
                    second->next = iter;
                    iter = second;
                    second = temp2;              
                } else {
                    // Insert into first at the beginning
                    temp = first;
                    temp2 = second->next;
                    first = second;
                    second->next = temp;
                    second = temp2;            
                }
            } else if (iter->next != NULL) {
                prev = iter;
                iter = iter->next;
            } else if (iter->next == NULL) {
                iter->next = second;
                second = NULL;
            }
        }
    }
};

Recursive Solution by Runhe Tian:

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *head = NULL;
     for(int i = 0; i < lists.size(); ++i)
   head = mergeTwoLists(head, lists[i]);
  return head;
    }

private: 
    ListNode *mergeTwoLists(ListNode *head1, ListNode *head2) {
  if (head1 == NULL || head2 == NULL)
   return head1 == NULL ? head2 : head1;

        if (head1 -> val < head2 -> val) {
   head1 -> next = mergeTwoLists(head1 -> next, head2);
            return head1;
  } else {
   head2 -> next = mergeTwoLists(head2 -> next, head1);
            return head2;
  }
 }
};

======== Using min heap (make_heap) =====

class Solution {
public:
    struct comp {
      bool operator() (ListNode *a, ListNode *b) {
          int first = (a != NULL ? a -> val: -1);
          int second = (b != NULL ? b -> val: -1);
          return first > second;
      }  
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = NULL, *head = NULL;
        
        make_heap(lists.begin(), lists.end(), comp());
        while (!lists.empty()) {
            ListNode *node = lists.front();
            pop_heap(lists.begin(), lists.end(), comp());
            
            lists.pop_back();
            if (node == NULL) {
                continue;
            }
            if (ans == NULL) {
                ans = new ListNode(node -> val);
                head = ans;
            } else {
                ans -> next = new ListNode(node -> val);
                ans = ans -> next;
            }         
            if (node -> next) {
                lists.push_back(node -> next);
                push_heap(lists.begin(), lists.end(), comp());
            }
        }
        return head;
    }
};

======== Priority queue by bangbingsyb ====
class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};

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

class comp {
    public:
        bool operator()(const ListNode *lhs, const ListNode *rhs) {
          int first = (lhs != NULL ? lhs -> val: INT_MIN);
          int second = (rhs != NULL ? rhs -> val: INT_MIN);
          return first > second;
        }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, comp> pq;
        ListNode *dummy = new ListNode(INT_MIN);
        ListNode *prev = dummy;
        
        for (auto node : lists) {
            pq.push(node);
        }
        
        while (!pq.empty()) {
            ListNode *node = pq.top();pq.pop();
            if (node == NULL) {
                continue;
            }
            dummy -> next = node;
            if (node -> next != NULL) {
                pq.push(node -> next);
            }
            dummy = dummy -> next;
        }
        return prev -> next;
    }
};


============ Another ========
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct comp {
    bool operator()(ListNode *a, ListNode *b) {
        return a -> val > b -> val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head = NULL, *trav = NULL;
        if (lists.size() == 0) {
            return head;
        }
        priority_queue<ListNode *, vector<ListNode *>, comp> pq;
        
        for (auto list : lists) {
            if (list != NULL) {
                pq.push(list);
            }
        }
        
        while (!pq.empty()) {
            ListNode *node = pq.top(); pq.pop();
            if (node -> next != NULL) {
                pq.push(node -> next);
            }
            if (trav == NULL) {
                head = node;
                trav = head;
            } else {
                trav -> next = node;
                trav = trav -> next;
            }
        }
        return head;
    }
};

======== Leetcode explanation =======

Solution


Approach 1: Brute Force

Intuition & Algorithm

Traverse all the linked lists and collect the values of the nodes into an array.
Sort and iterate over this array to get the proper value of nodes.
Create a new sorted linked list and extend it with the new nodes.


As for sorting, you can refer here for more about sorting algorithms.

Complexity Analysis


Time complexity : $O(N\log N)$ where $N$ is the total number of nodes.

Collecting all the values costs $O(N)$ time.
A stable sorting algorithm costs $O(N\log N)$ time.
Iterating for creating the linked list costs $O(N)$ time.



Space complexity : $O(N)$.

Sorting cost $O(N)$ space (depends on the algorithm you choose).
Creating a new linked list costs $O(N)$ space. 






Approach 2: Compare one by one

Algorithm

Compare every $\text{k}$ nodes (head of every linked list) and get the node with the smallest value.
Extend the final sorted linked list with the selected nodes.






















1 / 11



















Complexity Analysis


Time complexity : $O(kN)$ where $\text{k}$ is the number of linked lists.

Almost every selection of node in final linked costs $O(k)$ ($\text{k-1}$ times comparison).
There are $N$ nodes in the final linked list.



Space complexity :

$O(n)$ Creating a new linked list costs $O(n)$ space.
$O(1)$ It's not hard to apply in-place method - connect selected nodes instead of creating new nodes to fill the new linked list. 






Approach 3: Optimize Approach 2 by Priority Queue

Algorithm

Almost the same as the one above but optimize the comparison process by priority queue. You can refer here for more information about it.

Complexity Analysis


Time complexity : $O(N\log k)$ where $\text{k}$ is the number of linked lists.

The comparison cost will be reduced to $O(\log k)$ for every pop and insertion to priority queue. But finding the node with the smallest value just costs $O(1)$ time.
There are $N$ nodes in the final linked list.



Space complexity :

$O(n)$ Creating a new linked list costs $O(n)$ space.
$O(k)$ The code above present applies in-place method which cost $O(1)$ space. And the priority queue (often implemented with heaps) costs $O(k)$ space (it's far less than $N$ in most situations). 






Approach 4: Merge lists one by one

Algorithm

Convert merge $\text{k}$ lists problem to merge 2 lists ($\text{k-1}$) times. Here is the merge 2 lists problem page.

Complexity Analysis


Time complexity : $O(kN)$ where $\text{k}$ is the number of linked lists.

We can merge two sorted linked list in $O(n)$ time where $n$ is the total number of nodes in two lists.
Sum up the merge process and we can get: $O(\sum_{i=1}^{k-1} (i*(\frac{N}{k}) + \frac{N}{k})) = O(kN)$.



Space complexity : $O(1)$

We can merge two sorted linked list in $O(1)$ space. 






Approach 5: Merge with Divide And Conquer

Intuition & Algorithm

This approach walks alongside the one above but is improved a lot. We don't need to traverse most nodes many times repeatedly


Pair up $\text{k}$ lists and merge each pair.


After the first pairing, $\text{k}$ lists are merged into $k/2$ lists with average $2N/k$ length, then $k/4$, $k/8$ and so on.


Repeat this procedure until we get the final sorted linked list.



Thus, we'll traverse almost $N$ nodes per pairing and merging, and repeat this procedure about $\log_{2}{k}$ times.

{align = "center"}

Complexity Analysis


Time complexity : $O(N\log k)$ where $\text{k}$ is the number of linked lists.

We can merge two sorted linked list in $O(n)$ time where $n$ is the total number of nodes in two lists.
Sum up the merge process and we can get: $O\big(\sum_{i=1}^{log_{2}{k}}N \big)= O(N\log k)$



Space complexity : $O(1)$

We can merge two sorted linked lists in $O(1)$ space.