合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[

1->4->5,

1->3->4,

2->6

]

输出: 1->1->2->3->4->4->5->6

方法一：

使用vector数组存多个链表的所有节点，进行从小到大的排序，完成后再进行元素的指向，从第一个元素指向最后一个元素

bool cmp(ListNode *l1, ListNode *l2) { return l1 -> val < l2 -> val;
}ListNode* mergeKLists(vector<ListNode*>& lists) { vector<ListNode *> node_vec;for (int i = 0;i < lists.size();   i) { while(lists[i]){ node_vec.push_back(lists[i]);lists[i] = lists[i] -> next;}}if (node_vec.size() == 0) { return NULL;}//从小到大排序std::sort(node_vec.begin(), node_vec.end(), cmp);for(int i = 1;i < node_vec.size();   i) { node_vec[i-1] -> next = node_vec[i];}//将最后一个元素的next指针指向空node_vec[node_vec.size() - 1] -> next = NULL;return node_vec[0];
}

时间复杂度：

设有k个链表，平均每个链表有n个节点

kNlogkN kN = O(kNlogkN)

方法二：

分治法，即将所有链表分治合并为两个链表，再将两个链表合并为一个有序链表

实现如下:

//合并两个链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode new_head(0);ListNode *pre_new = &new_head;while(l1 && l2) { if (l1 -> val < l2 -> val) { pre_new -> next = l1;l1 = l1 -> next;} else { pre_new -> next = l2;l2 = l2 -> next;}pre_new = pre_new -> next;}if (l1) { pre_new -> next = l1;} if (l2) { pre_new -> next = l2;}return new_head.next;
}ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.size() == 0) return NULL;if (lists.size() == 1) return lists[0];if (lists.size() == 2) { return mergeTwoLists(lists[0],lists[1]);}int mid = lists.size() / 2;vector<ListNode *> sub_list1;vector<ListNode *> sub_list2;for (int i = 0;i < mid; i  ) { sub_list1.push_back(lists[i]);}for (int i = mid;i < lists.size();   i) { sub_list2.push_back(lists[i]);}/*分治链表节点，两两合并*/ListNode *l1 = mergeKLists(sub_list1);ListNode *l2 = mergeKLists(sub_list2);return mergeTwoLists(l1,l2);
}

时间复杂度：

设有k个链表，平均每个链表有n个节点

第1轮，进行k/2次，每次处理2n个数字;

第2轮，进行k/4次，每次处 理4n个数字;…;

最后一次，进行k/(2^{logk)次，每次处理2}logk*N个值。

2N*k/2 4N * k/4 8N * k/8 … 2^logk * N * k/(2^logk) =Nk Nk … Nk = O(kNlogk)

方法三：

使用队列，将K个链表插入队列，两两合并后放入队尾，直到队列中只有一个元素

实现如下:

ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.size() == 0) { return NULL;}if (lists.size() == 1) { return lists[0];}//将vector转为队列queue<ListNode*> waiting(deque<ListNode*>(lists.begin(), lists.end()));while(waiting.size() > 1) { ListNode *l1 = waiting.front();waiting.pop();ListNode *l2 = waiting.front();waiting.pop();ListNode *p = mergeTwoLists(l1,l2);//见如方法二中的实现waiting.push(p);}return waiting.front();
}

时间复杂度：

(k-1)*n (k - 2)*n … n = n(k-1)*k/2

O(nk^2)