题目描述：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题目翻译
给定k个有序链表,将其合并为一个有序的链表，并分析复杂度。
解题方案
标签： linked list
思路：
- 利用分治的思想把合并k个链表分成两个合并k/2个链表的任务，一直划分，直到任务中只剩一个链表或者两个链表。
- 假设每个链表的平均长度为n，则T(k,n) = 2T(k/2,n) + O(nk),很简单可以推导得到算法复杂度为O（nklogk）。
代码：
/**
* 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) {
int n = lists.size();
if(n == 0)return NULL;
while(n >1)
{
int k = (n+1)/2;
for(int i = 0; i < n/2; i++)
lists[i] = merge2list(lists[i], lists[i + k]);
n = k;
}
return lists[0];
}
ListNode *merge2list(ListNode *head1, ListNode*head2)
{
ListNode node(0), *res = &node;
while(head1 && head2)
{
if(head1->val <= head2->val)
{
res->next = head1;
head1 = head1->next;
}
else
{
res->next = head2;
head2 = head2->next;
}
res = res->next;
}
if(head1)
res->next = head1;
else if(head2)
res->next = head2;
return node.next;
}
};