LeetCode题目23：合并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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(-1);
        ListNode *p1 = l1, *p2 = l2, *q = head;
        int val = 0;
        while (p1 != NULL && p2 != NULL) {
            if (p1->val <= p2->val) {
                q->next = p1;
                p1 = p1->next;
            } else {
                q->next = p2;
                p2 = p2->next;
            }
            q = q->next;
        }

        q->next = p1 != NULL ? p1 : p2;

        return head->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists, int begin, int end) {
        if (begin > end) return NULL;
        if (begin == end) return lists[begin];
        int mid = (begin + end) / 2;
        return mergeTwoLists(mergeKLists(lists, begin, mid), mergeKLists(lists, mid + 1, end));
    }

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