LeetCode #23 – Merge k Sorted Lists [二分]

链接：https://leetcode.com/problems/merge-k-sorted-lists/

题目：Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

题意：给定k个有序链表，合并成一个有序链表

分析：类似上个合并两个链表的题目，对于k个链表，可以二分合并

CPP代码：

//struct ListNode {
//    int val;
//    ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;
        while(lists.size() >= 2) {
            int sz = lists.size();
            for(int i = 0, j; (j = sz - i - 1) > i; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[j]);
                lists.pop_back();
            }
        }
        return lists[0];
    }
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * head = new ListNode(0);
        ListNode * p = head;
        while(l1 != NULL || l2 != NULL) {
            if(l1 == NULL || (l2 != NULL && l2->val < l1->val)) {
                p->next = new ListNode(l2->val);
                l2 = l2->next;
            }
            else {
                p->next = new ListNode(l1->val);
                l1 = l1->next;
            }
            p = p->next;
        }
        return head->next;
    }
};