Java中的链表有快速连接方法吗？

Question

如何通过jdk1.6,google或apache commons集合或其他任何方式将O(1)中的两个链接列表与Java连接起来？例如,在jdk中,只有addAll方法是O(n).

我想念的另一个功能是连接两个列表,其中每个列表可以按相反的顺序排列.为了说明这一点,假设两个列表a-> b-> c和e-> f-> g可以合并为

1. A-> B-> C-> E-> F->克
2. A-> B-> C-> G-> F->电子
3. C-> B-> A-> E-> F->克
4. C-> B-> A-> G-> F->电子

你知道这样的列表实现还是我必须实现自己的链表？了解如何调整现有解决方案也很有帮助(例如,jdk LinkedList只有很多私有方法).这些功能在我看来非常明显,希望我不会错过一些愚蠢的东西.

正如MicSim指出的那样,在Java中使用Merge两个列表的常量时间是相关的,但不是真正的重复!现在的问题是:

1. 是否有可能与其他集合库？
2. 如何连续反转？

Answer 1

如果您愿意接受Iterable结果,可以使用google-collections Iterables.concat和Iterables.reverse

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Iterables.html

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c,
                                 Iterable<? extends T> d)

public static <T> Iterable<T> concat(Iterable<? extends T>... inputs)

public static <T> Iterable<T> concat(Iterable<? extends Iterable<? extends T>> inputs)

Answer 2

我目前看到的唯一解决方案是实现 List，创建一个构造函数，如下所示：

public EnhancedList (List l1, List l2)

并覆盖所有方法。在这样的解决方案中，无论您想要连接 LinkedList 还是任何其他列表，实际上并不重要。