[LeetCode]Merge k Sorted Lists

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 *merge(ListNode *head1,ListNode *head2)
	{
		if(head1==NULL) return head2;
		if(head2==NULL) return head1;
		ListNode *p=head1;
		ListNode *q=head2;
		ListNode *newhead=NULL;	
		ListNode *r=newhead;
		while(p&&q)
		{
			ListNode *newnode=new ListNode(NULL);
			if(p->val<q->val)
			{
				newnode=p;
				p=p->next;
			}
			else
			{
				newnode=q;
				q=q->next;
			}
			if(newhead==NULL)
			{
				newhead=newnode;
				r=newnode;
			}
			else
			{
				r->next=newnode;
				r=r->next;
			}
		}
		if(p) r->next=p;
		else  r->next=q;
		return newhead;		
	}
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        ListNode *newhead=NULL;
		for(int i=0;i<lists.size();i++)
		{
			newhead=merge(newhead,lists[i]);
		}
		return newhead;
    }
};