分治算法

leetode23-合并k个排序链表

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
输入:
[1->4->5,
1->3->4,
2->6]
输出: 1->1->2->3->4->4->5->6

代码

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right) {
        if (right < left) return NULL;
        if (right == left) return lists[left];

        int mid = (left + right) / 2;
        auto p1 = mergeKLists(lists, left, mid);
        auto p2 = mergeKLists(lists, mid + 1, right);

        ListNode head(0);
        ListNode* cur = &head;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                cur->next = p1;
                p1 = p1->next;
            } else {
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }

        if (p1) cur->next = p1;
        else if (p2) cur->next = p2;
        return head.next;
    }

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