题目描述：
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
C++代码如下：
class Solution {
public:
ListNode
* mergeKLists(vector
<ListNode
*>& lists
) {
if (lists
.empty()) return NULL
;
int n
= lists
.size();
while (n
>1){
int k
= (n
+1)/2;
for (int i
= 0; i
<n
/2; ++i
){
lists
[i
] = mergeTwoLists(lists
[i
],lists
[i
+k
]);
}
n
= k
;
}
return lists
[0];
}
ListNode
* mergeTwoLists( ListNode
*l1
, ListNode
*l2
){
ListNode
*temp
= new ListNode(-1) ,*p
= temp
;
while (l1
&& l2
){
if (l1
->val
< l2
->val
){
p
->next
= l1
;
l1
= l1
->next
;
}
else{
p
->next
= l2
;
l2
= l2
->next
;
}
p
= p
->next
;
}
if (l1
) p
->next
= l1
;
if (l2
) p
->next
= l2
;
return temp
->next
;
}
};
