Merge K sorted linked lists

problem

Ideas

Because the code parameter is directly given to an array , Therefore, each node can be regarded as a linked list , Then merge every two nodes , Form a new linked list , Merge with the next node , You can achieve the whole K A combination of linked lists . But this method will time out , unable ac. Therefore, the array is divided into two from the middle , Until it is divided into individual nodes . Finally, connect the individual nodes , Get the merged K A linked list .

Code implementation

/** * 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) {
    
        return divMerge(lists, 0, lists.size() - 1);
    }
    
    //  Split the array in half into elements , Re merger 
    ListNode* divMerge(vector<ListNode*> &lists, int left, int right)
    {
    
        if (left > right) return NULL;
        if (left == right) return lists[left];
        
        int mid = left + (right - left) / 2;
        return mergeTwoList(divMerge(lists, left, mid), divMerge(lists, mid + 1, right));
    }
    
    //  Merge two linked lists 
    ListNode* mergeTwoList(ListNode* p1, ListNode* p2)
    {
    
        ListNode* ret = new ListNode(0);
        ListNode* cur = ret;
        while (p1 && p2)
        {
    
            if (p1->val < p2->val)
            {
    
                cur->next = p1;
                p1 = p1->next;
            }
            else
            {
    
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }
        if (p1)
        {
    
            cur->next = p1;
        }
        if (p2)
        {
    
            cur->next = p2;
        }
        
        return ret->next;
    }
};