Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题目意思：
合并K条已经排序的链表。分析时间复杂度。
解题思路：
很容易就想起之前学的合并两条链表的算法，这一题其实就是那个题目的扩展，变成合并K条了。我采用的方法就是迭代法。
如果只有一条，直接返回。如果只有两条，就只需要调用mergeTwo一下。如果超过两条链表的话，先将前两个链表调用mergeTwo，然后用新的链表和第三个链表调用mergeTwo，再用结果和第四个链表调用mergeTwo，依次调用到最后一个链表。
时间复杂度貌似是O（n2）……有点慢。Orz~不过AC了。
有一点就是我这里用来合并两个链表的方法mergeTwo是用递归实现的（《剑指offer》第116页中代码），课本上是用循环的。大家可以参考一下。
其实更有效率的方法就是归并法，即先lists分成一半，再分成一半，直到分成只有两个了再调用一下mergeTwo。这样效率会高很多。mark一下，该方法代码以后看心情补上。
代码如下：
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if(lists.size() == ){
return lists[];
}
if(lists.size() == ){
ListNode *ret;
ret = mergeTwo(lists[],lists[]);
return ret;
}
if(lists.size() > ){
ListNode *p = NULL;
p = mergeTwo(lists[],lists[]);
for(int i = ; i < lists.size(); i++){
p = mergeTwo(p,lists[i]);
}
return p;
}
}
ListNode *mergeTwo(ListNode *list1,ListNode *list2){
//合并list1和list2，返回新的list3的头结点指针
if(list1 == NULL){
return list2;
}
else if(list2 == NULL){
return list1;
}
ListNode *list3 = NULL;
if(list1->val < list2->val){
list3 = list1;
list3->next = mergeTwo(list1->next,list2);
}
else{
list3 = list2;
list3->next = mergeTwo(list1,list2->next);
}
return list3;
}
};