要求合并k个有序链表节点到一个链表之中。可以使用如下的方法进行合并：
1. 分治算法
2. 最小堆K路合并
思路：
1. 分治算法类似归并排序，我们对于合并两个有序链表是可以快速解决的，那么我们可以不断的对集合进行划分，直到集合中的链表条数为1或者2，如果是1直接返回就行，如果是2则合并后再返回。然后依次往上合并，最终就可以得到结果。
2. 最小堆K路归并，从每一条链表中取出第一个节点，创建一个最小堆，取出最小堆中的第一个节点，然后从被取出节点原来所在的链表中取出第一个节点放入堆中，不断的重复这个过程。
直到：某一条链表没有节点了，这时候把堆的最后一个节点放入到堆的第一个节点，然后堆的带下减去1，然后维持堆的性质，这个过程不断重复，直到：堆中没有元素。
复杂度：
1. 分治算法
待分析
2. 最小堆K路归并
O(nlgk) 这个比较好理解，代码写出来就看得出了。
首次从K条链表每个取出一个元素，O(k)
建堆：O(k)
维护：从链表中取出一个元素放到堆，并维护堆的性质，如果元素总数为n，则为nlgk
时间复杂度：O(k) + O(nlgk)
阅读(339) | 评论(0) | 转发(0) |
