题解 | #合并k个已排序的链表#

/**
 * 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) {
        
        // 定义递归函数，经过该函数后，l到r范围内的各个列表成功合并成一个有序链表
        return recursion(lists,0,lists.size()-1);
        
    }
    ListNode* recursion(vector<ListNode*> &lists,int l,int r){
        
        // 递归终点
        if(l > r)
            return NULL;
        
        else if( l == r)
            return lists[l];
        
        int mid = l + (r - l)/2;

        return merge(recursion(lists, l, mid) , recursion(lists, mid+1 , r));
        
    }
    ListNode* merge(ListNode* p1, ListNode* p2){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        
        while(p1 && p2){
            if( p1->val <= p2->val ){
                cur->next = p1;
                p1 = p1->next;
            }
            else{
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }
        
        cur->next = p1 ? p1 : p2;
        
        return dummy->next;
    }
};