Merge k Sorted Lists

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

struct Node{	int val;	Node *next;	Node(int x) : val(x), next(NULL){}};Node* merge(vector<Node*> &lists, int left, int right){	if (left == right)	{		return lists[left];	}	int mid = left + (right-left)/2;	Node *p = merge(lists, left, mid);	Node *q = merge(lists, mid+1, right);	Node *PRev = NULL;	Node *head = NULL;	while (p && q)	{		Node *cur = p;		if (p->val <= q->val)		{			cur = p;			p = p->next;		}		else		{			cur = q;			q = q->next;		}		if (head == NULL)		{			head = cur;			prev = head;		}		else		{			prev->next = cur;			prev = cur;		}	}	if (p == NULL)	{		prev->next = q;	}	else if (q == NULL)	{		prev->next = p;	}	return head;}Node* mergeList(vector<Node*> &lists){	return merge(lists, 0, lists.size()-1);}