在java中合并两个排序的链接列表

Question

我需要将两个排序链接列表合并成一个排序列表。我已经尝试了好几个小时了，但是当我到达列表的末尾时，我总是会遇到一些麻烦。这是我能做的最好的了。我的filaA和filaB喜欢数据类型"long“的列表。

            LinkedList<Long> result= new LinkedList<Long>();
            iterA = filaA.listIterator();
            iterB = filaB.listIterator();
            while (iterA.hasNext() && iterB.hasNext()) {
                n = iterA.next();
                m = iterB.next();
                if (n <= m) {
                    filafusion.add(n);
                    n = iterA.next();
                } else {
                    filafusion.add(m);
                    m = iterB.next();
                }
            }
            if (iterA.hasNext()) {
                while (iterA.hasNext()) {
                    filafusion.add(iterA.next());
                }
            } else {
                while (iterB.hasNext()) {
                    filafusion.add(iterB.next());
                }
            }
            iterfusion = filafusion.listIterator();
            while (iterfusion.hasNext()) {
                System.out.print(iterfusion.next());
            }
        }

这里的一般想法是逐个比较，然后将迭代器移到下一个迭代器。但是它们同时移动，所以我只比较第一和第一，第二和第二，等等。

我还尝试在while循环之前移动n = iterA.next();m = iterB.next();，这使得它工作得更好，但是我不知道哪一个列表会耗尽元素。只有在列表长度相同的情况下才能工作，但是其中一个元素不会输入结果。

我在这里看到了很多代码，但是它们都使用节点和递归以及一些我不熟悉的东西。我认为使用迭代器会使它更有效率，但这就是让我感到困惑的原因，我没有在应该迭代的地方进行迭代：

如有任何建议，将不胜感激。

Answer 1

我只是修改了你的代码。如果您能够使用Java 8，那么下面有一个更短的解决方案。

    Iterator iterA = filaA.listIterator();
        Iterator iterB = filaB.listIterator();
        Long n = (Long)iterA.next();
        Long m = (Long)iterB.next();
        while (true) {
            if (n <= m) {
                filafusion.add(n);
                if(iterA.hasNext()){
                    n = (Long)iterA.next();
                }
                else{
                    filafusion.add(m);
                    while(iterB.hasNext()){
                        filafusion.add((Long)iterB.next());
                    }
                    break;
                }
            } else {
                filafusion.add(m);
                if(iterB.hasNext()){
                    m = (Long)iterB.next();
                }
                else{
filafusion.add(n);
                    while(iterA.hasNext()){
                        filafusion.add((Long)iterA.next());
                    }
                    break;
                }

            }
        }
        Iterator iterfusion = filafusion.listIterator();
        while (iterfusion.hasNext()) {
            System.out.println(iterfusion.next());
        }

以下是Java 8的实现方法。它也适用于未排序的输入列表：

    Stream stream = Stream.concat(filaA.stream(), filaB.stream());
    stream.sorted().forEach(System.out::println);

Answer 2

您可以使用标准的java.util.TreeSet来完成这项工作。

下面是一个完整的例子：

    LinkedList<Long> filaA = new LinkedList<>();
    filaA.add(1l);
    filaA.add(3l);
    filaA.add(5l);
    LinkedList<Long> filaB = new LinkedList<>();
    filaB.add(2l);
    filaB.add(4l);
    filaB.add(6l);

    Set<Long> result = new TreeSet<>();
    result.addAll(filaA);
    result.addAll(filaB);
    System.out.println(result);

TreeSet使用自然顺序。

Answer 3

public static <T extends Comparable<T>> List<T> mergeSortedLists(List<T> list1, List<T> list2) {
    List<T> result = new ArrayList<>();
    Iterator<T> iterator1 = list1.iterator();
    Iterator<T> iterator2 = list2.iterator();
    boolean hasNext1 = iterator1.hasNext();
    boolean hasNext2 = iterator2.hasNext();
    T next1 = hasNext1 ? iterator1.next() : null;
    T next2 = hasNext2 ? iterator2.next() : null;
    while (hasNext1 || hasNext2) {
        if (!hasNext1) {
            result.add(next2);
            hasNext2 = iterator2.hasNext();
            next2 = hasNext2 ? iterator2.next() : null;
        } else if (!hasNext2) {
            result.add(next1);
            hasNext1 = iterator1.hasNext();
            next1 = hasNext1 ? iterator1.next() : null;
        } else {
            if (next1.compareTo(next2) < 0) {
                result.add(next1);
                hasNext1 = iterator1.hasNext();
                next1 = hasNext1 ? iterator1.next() : null;
            } else {
                result.add(next2);
                hasNext2 = iterator2.hasNext();
                next2 = hasNext2 ? iterator2.next() : null;
            }
        }
    }
    return result;
}