/**
 * 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)
    {
        if (lists.empty())
		    return nullptr;

        ListNode* listNodeRet = nullptr;
        ListNode* listNodeHelp = nullptr;
        ListNode* listNodeMin = lists[0];
        size_t lastI = 0;
        bool isAnyListNotNullptr = false;

        do
        {
            isAnyListNotNullptr = false;
            for (size_t i = 0; i < lists.size(); ++i)
            {
                if (lastI == i)
                    continue;
                ListNode* listsI = lists[i];
                if (!listsI)
                    continue;
                if (!listNodeMin)
                {
                    listNodeMin = listsI;
                    lastI = i;
                    continue;
                }

                isAnyListNotNullptr = true;

                if (listsI->val < listNodeMin->val)
                {
                    listNodeMin = listsI;
                    lastI = i;
                }
            }

            if (!listNodeRet)
            {
                listNodeRet = listNodeMin;
                listNodeHelp = listNodeRet;
            }
            else
            {
                listNodeHelp->next = listNodeMin;
                listNodeHelp = listNodeHelp->next;
            }

            if (listNodeMin)
                listNodeMin = listNodeMin->next;
            if (lists[lastI])
                lists[lastI] = lists[lastI]->next;

        } while (isAnyListNotNullptr);

        return listNodeRet;
    }
};