23.合并k个排序链表

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解决方案

我们采用二分法与迭代法来解决该问题，每次讲两个链表合并成一个链表后，将得到的新链表继续进行与下一个链表进行合并，具体代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoList(ListNode* l1,ListNode* l2){
        ListNode *node = new ListNode(-1);
        ListNode *cur = node;

        while(l1&&l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return node->next;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() ==0){
            return NULL;
        }
        if(lists.size()==1){
            return lists[0];
        }
        
        int len = lists.size();
        while(len>1){
            int n = (len+1)/2;
            for(int i=0;i<len/2;++i){            
                lists[i] = mergeTwoList(lists[i],lists[i+n]);
            }
            len = n;
        }
        
        return lists[0];
    }
};