力扣23题，合并K个升序链表

力扣23题，合并K个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入输出样例

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

输入：lists = []
输出：[]

输入：lists = [[]]
输出：[]

解法一，（顺序合并）

//合并k个升序链表
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];
    //设置标志位

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

    // cout<<"合并后的list元素: ";
    // 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;
    }

}

采用leetcode23题中的方法，首先对两个链表进行递归合并，然后在推广到三个，四个以及多个链表的合并。

解法二：使用分治算法

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];

}

分治算法相较于顺序合并就是一个逐次进行两两匹配的过程。