leetcode23. 合并 K 个升序链表

题目

题解

递归+分治

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode*mergeTwoLists(ListNode*p,ListNode*q){
        ListNode*dummy=new ListNode();
        ListNode*tail =dummy;
        while(p&&q){
            if(p->val<q->val){
                tail->next=p;
                p=p->next;
                tail=tail->next;
            }else{
                tail->next=q;
                q=q->next;
                tail=tail->next;
            }
        }
        if(p)tail->next=p;
        if(q)tail->next=q;
        return dummy->next;
    }
      ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists,0,lists.size()-1);
    }
};