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

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *mergeTwoList(ListNode * head1,ListNode * head2)    {        if(head1 == NULL)            return head2;        if(head2 == NULL)            return head1;                ListNode *root = new ListNode(0);        ListNode *p = root;        while(head1  && head2 )        {            if(head1->val < head2->val)            {                p->next = head1;                p = p->next;                head1 = head1->next;                                  }            else            {                p->next = head2;                p = p->next;                head2 = head2->next;                                  }                      }                while(head1)        {            p->next = head1;            p = p->next;            head1 = head1->next;                    }                while(head2)        {            p->next = head2;            p = p->next;            head2 = head2->next;                }        return root->next;         }                ListNode *mergeKLists(vector
    
      &lists) {        if( ! lists.size())            return NULL;        if(lists.size() == 1)            return lists[0];        ListNode * root = lists[0];        for(int i = 1;i < lists.size();i ++)        {            root = mergeTwoList(root,lists[i]);                      }                return root;                    }};