leetcode Question 52: Merge k Sorted Lists

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

Analysis:
While the lists is not empty, keep merging the list to the result list. Method to merge two lists is the same as Question 54

Code(updated 201309):

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* head=new ListNode(0);
        if (lists.size()==0){return NULL;}
        head->next = lists[0];
        ListNode *p;
        ListNode *q;
        for (int i=1;i<lists.size();i++){
            p = head;
            q = lists[i];
            while (q){
                if (!p->next){
                    p->next = q;
                    break;
                }
                if (p->next->val<q->val){
                    p=p->next;
                }else{
                    ListNode *l = p->next;
                    p->next = q;
                    q=q->next;
                    p->next->next = l;
                    p=p->next;
                }
            }
        }
        return head->next;
    }
};

Code(old version):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merg2(ListNode* l1, ListNode* l2){
        ListNode* head = new ListNode(0);
        head->next = l1;
        ListNode* prev = head;
        if (l1==NULL){
            head->next=l2;
        }
        while (l1!=NULL && l2!=NULL){
            if (l1->val < l2->val){
                if (l1->next != NULL){
                    prev = l1;
                    l1=l1->next;
                }else{
                    l1->next = l2;
                    break;
                }
            }else{
                ListNode* tmp = l2->next;
                prev->next = l2;
                l2->next = l1;
                prev = l2;
                l2 = tmp;
            }
        }
        return head->next;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (lists.empty()){return NULL;}
        ListNode *head = lists.back();
        lists.pop_back();
        while (!lists.empty()){
            head = merg2(head,lists.back());
            lists.pop_back();
        }
        return head;
    }