17. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

Solution : (Merge one by one)

class Solution
{
public:
    ListNode *mergeList(ListNode *l1, ListNode *l2)
    {
        if (l1 == NULL)
        {
            return l2;
        }
        if (l2 == NULL)
        {
            return l1;
        }

        ListNode *sort = NULL;
        ListNode *head = NULL;

        if (l1->val <= l2->val)
        {
            sort = l1;
            l1 = l1->next;
        }
        else if (l2->val < l1->val)
        {
            sort = l2;
            l2 = l2->next;
        }
        head = sort;

        while (l1 != NULL && l2 != NULL)
        {
            if (l1->val <= l2->val)
            {
                sort->next = l1;
                sort = sort->next;
                l1 = l1->next;
            }
            else
            {
                sort->next = l2;
                sort = sort->next;
                l2 = l2->next;
            }
        }

        if (l1 == NULL)
        {
            sort->next = l2;
        }
        else
        {
            sort->next = l1;
        }

        return head;
    }

    ListNode *mergeKLists(vector<ListNode *> &lists)
    {

        ListNode *res = NULL;

        if (lists.size() == 0)
        {
            return res;
        }
        if (lists.size() == 1)
        {
            res = lists[0];
            return res;
        }

        ListNode *l1 = lists[0];
        ListNode *l2 = lists[1];

        res = mergeList(l1, l2);

        for (int i = 2; i < lists.size(); i++)
        {
            res = mergeList(res, lists[i]);
        }

        return res;
    }
};

Time Complexity: O(k N)

Solution: (Merge with Divide And Conquer)

class Solution
{
public:
    ListNode *mergeList(ListNode *l1, ListNode *l2)
    {
        if (l1 == NULL)
        {
            return l2;
        }
        if (l2 == NULL)
        {
            return l1;
        }

        ListNode *sort = NULL;
        ListNode *head = NULL;

        if (l1->val <= l2->val)
        {
            sort = l1;
            l1 = l1->next;
        }
        else if (l2->val < l1->val)
        {
            sort = l2;
            l2 = l2->next;
        }
        head = sort;

        while (l1 != NULL && l2 != NULL)
        {
            if (l1->val <= l2->val)
            {
                sort->next = l1;
                sort = sort->next;
                l1 = l1->next;
            }
            else
            {
                sort->next = l2;
                sort = sort->next;
                l2 = l2->next;
            }
        }

        if (l1 == NULL)
        {
            sort->next = l2;
        }
        else
        {
            sort->next = l1;
        }

        return head;
    }

    ListNode *mergeKLists(vector<ListNode *> &lists)
    {

        ListNode *res = NULL;

        if (lists.size() == 0)
        {
            return res;
        }
        if (lists.size() == 1)
        {
            res = lists[0];
            return res;
        }

        int last = lists.size() - 1;

        while (last != 0)
        {
            int i = 0;
            int j = last;

            while (i < j)
            {
                lists[i] = mergeList(lists[i], lists[j]);
                i++;
                j--;
            }

            last = j;
        }

        return lists[0];
    }
};

Time Complexity: O(N log k)