k路已排序链表的合并O(nlgk)

题目：请给出一个时间为O(nlgk)、用来将k个已排序链表合并为一个排序链表的算法。此处n为所有输入链表中元素的总数。

(机械工业出版社 《算法导论》P82  6.5-8)

 

这是网上找到一个解答：

1.把每个已排序链表的第一个值取下，构建一个k个元素的最小堆。

2.找到最小元素原来的链表，从中取下第二个元素，插入最小堆。

3.接着找到当前最小元素原来的链表，从中取下下一个元素，插入最小堆。

4.循环直到所有链表为空。

 

这里我有个疑问:

第三步是不是可以替换成随便从k个链表中取出一个元素，插到最小堆里，这样时间复杂度也是O(nlgk)。可是这样的话就完全没有到每个链表是有序的这个特性了。

不可以随便取出一个元素，必须在当前最小元素所在的链表，这样才能保证最小堆里的最小值就是所有剩下元素之中的最小值

二楼威武啊！说的太好了，可是怎么标记被取走的节点来自哪个链表呢？

开始绞尽脑汁也没明白！

使用二路归并就好了，其算法时间复杂度就是O(N*logN)。思路是一样的，不过如其名，就是将有序列两两合并，最后合成一个，实现起来简单点。

 

貌似LZ的空间也有归并排序的算法了...估计我没理解帖子的意思...代码不贴了。

不知道是否是这个意思？

import java.util.ArrayList;
import java.util.List;

public class SortOrderArrTest {

        /**
         * @param args
         * @description 方法说明
         */
        public static void main(String[] args) {
                int[] a = new int[]{9,10,200};
                int[] b = new int[]{1,44,55,201,233,};
                int[] c = new int[]{13,34,85,103,333,};
                List<int[]> aList = new ArrayList<int[]>();
                aList.add(a);
                aList.add(b);
                aList.add(c);
                
                int[] resultArr = sort(aList);
                for(int i : resultArr){
                        System.out.println(i);
                }
        }

        private static int[] sort(List<int[]> arrList) {
                List<int[]> tempList = new ArrayList<int[]>();
                for (int i = 0; i < arrList.size(); i += 2) {
                        int[] firstArr = arrList.get(i);
                        if (i == arrList.size() - 1) {
                                tempList.add(firstArr);
                                break;
                        }

                        int[] secondArr = arrList.get(i + 1);

                        int[] tempArr = compareArr(firstArr, secondArr);
                        tempList.add(tempArr);
                }

                if (tempList.size() > 1)
                        return sort(tempList);
                else
                        return tempList.get(0);

        }

        private static int[] compareArr(int[] firstArr, int[] secondArr) {
                int[] retArr = new int[firstArr.length + secondArr.length];

                int i = 0, j = 0;
                for (int m = 0; m < retArr.length; m++) {
                        if (i >= firstArr.length) {
                                if (j >= secondArr.length) {
                                        break;// 不应该进入此处，这样写的目的是为了逻辑严密
                                } else {
                                        copy(secondArr, j, retArr, m);
                                        break;
                                }
                        } else {
                                if (j >= secondArr.length) {
                                        copy(firstArr, i, retArr, m);
                                        break;
                                }
                        }

                        int first = firstArr[i];
                        int second = secondArr[j];
                        if (first <= second) {
                                retArr[m] = first;
                                i++;
                        } else {
                                retArr[m] = second;
                                j++;
                        }
                }
                return retArr;
        }

        private static void copy(int[] fromArr, int fromStartIndex, int[] toArr, int toStartIndex) {
                for (int i = fromStartIndex; i < fromArr.length; i++) {
                        toArr[toStartIndex++] = fromArr[i];
                }
        }

}

运行结果：
1
9
10
13
34
44
55
85
103
200
201
233
333