Merge_k_sorted_list

/*
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 *mergeKLists(vector<ListNode *> &lists) {
      if (lists.size()==0) return NULL;
      if (lists.size()==1) return lists[0];
      ListNode *head=new ListNode(INT_MIN);
      head->next=lists[0];
      for (int i=1; i<lists.size(); ++i)
      {
          ListNode *p1=head->next,*p2=lists[i],*p=head;
          while(p1 && p2)
          {
              if (p1->val<=p2->val) 
              {
                  p->next=p1;
                  p=p1;
                  p1=p1->next;
              }
              else
              {
                  p->next=p2;
                  p=p2;
                  p2=p2->next;
              }
          }
          if (!p1) p->next=p2;
          if (!p2) p->next=p1;
      }
      return head->next;
    }
};


REMARK:
1. Medium difficulty. Thought for a while.Shouldn't have thought that long.
IDEA: Simple. Since we know how to merge 2 sorted list(a simpler problem that I did before in leetcode),we merge the 1st and 2nd list into a new list, then merge the new list with the 3rd list into a new one, then merge the new one with the 4th list and so forth.
2.Time complexity: O(n1+...+nk) where ni is the length of the lists[i].