Force deduction 23 questions, merging K ascending linked lists

Power button 23 topic , Merge K An ascending list

Title Description

Here's an array of linked lists , Each list has been listed in ascending order . Please merge all the linked lists into one ascending list , Return the merged linked list .

I/o sample

 Input ：lists = [[1,4,5],[1,3,4],[2,6]]
 Output ：[1,1,2,3,4,4,5,6]
 explain ： The linked list array is as follows ：
[
  1->4->5,
  1->3->4,
  2->6
]
 Combine them into an ordered list to get .
1->1->2->3->4->4->5->6

 Input ：lists = []
 Output ：[]

 Input ：lists = [[]]
 Output ：[]

Solution 1 ,（ Order merge ）

// Merge k An ascending list 
ListNode *mergeKLists(vector<ListNode*>&lists)
{
    
    ListNode* resList;
    int length=lists.size();
    if(length==0)
    {
    
        return resList=nullptr;
    }
    else if(length==1)
    {
    
        resList=lists[0];
        return resList;
    }

    resList=lists[0];
    // Set flag bit 

    for(int i=1;i<length;i++)
    {
    
        resList=mergeList(resList,lists[i]);
    }
    // resList=mergeList(lists[0],lists[1]);

    // cout<<" After the merger list Elements : ";
    // printList(resList->next);
    return resList;
}


ListNode *mergeList(ListNode *list1,ListNode *list2)
{
    
    if(list1==nullptr)
    {
    
        return list2;
    }
    else if(list2==nullptr)
    {
    
        return list1;
    }
    else if(list1->val<list2->val)
    {
    
        list1->next=mergeList(list1->next,list2);
        return list1;
    }
    else 
    {
    
        list2->next=mergeList(list1,list2->next);
        return list2;
    }

}

use leetcode23 Method in question , First, recursively merge the two linked lists , Then it is extended to three , Consolidation of four or more linked lists .

Solution 2 ： Using divide and conquer algorithm

ListNode *mergeKList2(vector<ListNode*>&lists)
{
    
    int length=lists.size();
    ListNode* resList;
    if(length==0)
    {
    
        return resList=nullptr;
    }
    else if(length==1)
    {
    
        resList=lists[0];
        return resList;
    }

    int interval=1;
    while(interval<length)
    {
    
        for(int i=0;i<length-interval;i=i+2*interval)
        {
    
            lists[i]=mergeList(lists[i],lists[i+interval]);            
        }
        interval*=2;
    }
    return lists[0];

}

Divide and conquer algorithm is a process of pairwise matching step by step compared with sequential merging .