Kotlin 或 Java 中恒定时间复杂度 O(1) 的 Concat 链表

Question

我正在做的是连接动态生成的链表，一次只有 2 个。如何在 Kotlin 或 Java 中以恒定时间复杂度 O(1) 做到这一点？

Java中的这个类似问题告诉我java.util.LinkedList不支持在恒定时间内添加。而且 Google GuavaIterators.concat只能在一次调用中组合 2 个或更多迭代器，这会导致多层包装并在我的情况下迭代时增加复杂性。

Answer 1

在 Kotlin 中，您可以Iterator使用如下函数组合多个 s iterator {...}：fun <T> combine(a: Iterator<T>, b: Iterator<T>, c: Iterator<T>): Iterator<T> {&nbsp; return iterator {&nbsp; &nbsp; yieldAll(a)&nbsp; &nbsp; yieldAll(b)&nbsp; &nbsp; yieldAll(c)&nbsp; }}这个函数返回一个Iterator类型，然后和最后T延迟消耗abc解决方案是这样的：fun <T> combine(vararg iterators: Iterator<T>): Iterator<T> {&nbsp; return iterator {&nbsp; &nbsp; iterators.forEach { yieldAll(it) }&nbsp; }}此实现采用n迭代器并将它们组合成一个。

Answer 2

我已经实现了一个基于 Java 的简单版本的单链表，LinkedList只是为了支持这个 concat 函数。为简单起见，它只实现Iterable而不是List：Java实现：import java.util.Iterator;import java.util.NoSuchElementException;public class SimpleLinkedList<E> implements Iterable<E> {&nbsp; &nbsp; Node<E> first;&nbsp; &nbsp; Node<E> last;&nbsp; &nbsp; static class Node<E> {&nbsp; &nbsp; &nbsp; &nbsp; E item;&nbsp; &nbsp; &nbsp; &nbsp; Node<E> next;&nbsp; &nbsp; &nbsp; &nbsp; Node(E item, Node<E> next) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.item = item;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.next = next;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; static class NodeIterator<E> implements Iterator<E> {&nbsp; &nbsp; &nbsp; &nbsp; private Node<E> node;&nbsp; &nbsp; &nbsp; &nbsp; NodeIterator(Node<E> node) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.node = node;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public boolean hasNext() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node != null;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public E next() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node<E> currentNode = node;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (currentNode == null) throw new NoSuchElementException();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = currentNode.next;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return currentNode.item;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public Iterator<E> iterator() {&nbsp; &nbsp; &nbsp; &nbsp; return new NodeIterator<>(first);&nbsp; &nbsp; }&nbsp; &nbsp; public void add(E element) {&nbsp; &nbsp; &nbsp; &nbsp; // Copied from java.util.LinkedList&nbsp; &nbsp; &nbsp; &nbsp; Node l = last;&nbsp; &nbsp; &nbsp; &nbsp; Node<E> newNode = new Node<>(element, null);&nbsp; &nbsp; &nbsp; &nbsp; last = newNode;&nbsp; &nbsp; &nbsp; &nbsp; if (l == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; first = newNode;&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.next = newNode;&nbsp; &nbsp; }&nbsp; &nbsp; public void concatWith(SimpleLinkedList other) {&nbsp; &nbsp; &nbsp; &nbsp; if (last != null) last.next = other.first;&nbsp; &nbsp; &nbsp; &nbsp; else first = other.first;&nbsp; &nbsp; &nbsp; &nbsp; if (other.last != null) last = other.last;&nbsp; &nbsp; }}Kotlin 实现：class SimpleLinkedList<E> : Iterable<E> {&nbsp; &nbsp; var first: Node<E>? = null&nbsp; &nbsp; var last: Node<E>? = null&nbsp; &nbsp; class Node<E>(var item: E, var next: Node<E>? = null)&nbsp; &nbsp; class NodeIterator<E>(var node: Node<E>?) : Iterator<E> {&nbsp; &nbsp; &nbsp; &nbsp; override fun hasNext(): Boolean = node != null&nbsp; &nbsp; &nbsp; &nbsp; override fun next(): E {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; val currentNode = node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (currentNode === null) throw NoSuchElementException()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = currentNode.next&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return currentNode.item&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; override fun iterator(): Iterator<E> = NodeIterator(first)&nbsp; &nbsp; fun add(element: E) {&nbsp; &nbsp; &nbsp; &nbsp; // Copied from java.util.LinkedList&nbsp; &nbsp; &nbsp; &nbsp; val l = last&nbsp; &nbsp; &nbsp; &nbsp; val newNode = Node(element, null)&nbsp; &nbsp; &nbsp; &nbsp; last = newNode&nbsp; &nbsp; &nbsp; &nbsp; if (l == null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; first = newNode&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.next = newNode&nbsp; &nbsp; }&nbsp; &nbsp; infix fun concatWith(other: SimpleLinkedList<E>) {&nbsp; &nbsp; &nbsp; &nbsp; last.run {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (this !== null) next = other.first&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else first = other.first&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; other.last?.let { last = it }&nbsp; &nbsp; }}Kotlin 实现实际上比 Java 慢一点，因为 getter 和 setter 用于访问属性。