merge k sorted list

code

/**
 * 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) {
        if(lists.size() == 0)
        {
            return NULL;
        }

        int n = lists.size();

        return helper(lists, 0, n-1);
    }

    ListNode* helper(vector<ListNode*>& lists, int s, int e)
    {
        if(s == e)
        {
            return lists[s];
        }

        if(s + 1 == e)
        {
            return mergeTwoLists(lists[s], lists[e]);
        }

        int mid = (s + e) / 2;

        ListNode* left = helper(lists, s, mid);
        ListNode* right = helper(lists, mid+1, e);

        return mergeTwoLists(left, right);
    }

    ListNode* mergeTwoLists(ListNode* left, ListNode* right)
    {
        ListNode dummy(0);
        ListNode* p = &dummy;

        while(left != NULL && right != NULL)
        {
            if(left->val < right->val)
            {
                p->next = left;
                left = left->next;
            }
            else
            {
                p->next = right;
                right = right->next;
            }

            p = p->next;
        }

        if(left != NULL)
        {
            p->next = left;
        }

        if(right != NULL)
        {
            p->next = right;
        }

        return dummy.next;
    }
};