我的一个作业问题是编写一个算法来反转 LinkedList，在 θ(N) 时间内生成一个新列表。
我提出的代码不符合时间要求，我无法找出原因。
public Node reverse() {
if (this == Node.NIL) {
return Node.NIL;
}
if (this.getNext() == Node.NIL) {
return new Node(this.getItem(), this.getNext());
}
Node curNode = new Node(this.getItem(), this.getNext());
Node front = curNode;
Node nextNode = null;
Node prevNode = null;
while (curNode.getNext() != Node.NIL) {
nextNode = new Node(curNode.next.item, curNode.next.next);
curNode.next = prevNode;
prevNode = curNode;
curNode = nextNode;
}
curNode.next = prevNode;
front.setNext(Node.NIL);
return curNode;
}
有一个名为 NIL 的节点，应称为 Node.NIL，它始终是提供的要反转的列表中创建的第一个节点，因此如果 Node.NIL 是下一个节点，您将位于列表的末尾.
每个节点都有 2 个属性，“next”和“item” - “next”是列表中的下一个节点，“item”是它携带的数据，在本例中是一个对象。
这是正在使用的测试 (NCASES = 20):
@Test
public void testReverseTiming() {
int i;
long diff = 0;
for (i = 0; i < NCASES - 1; i++) {
long start = System.nanoTime();
Node result = nodes2[i].reverse();
long end = System.nanoTime();
diff = end - start;
if (diff/1000000 > 250) {
i++;
break;
}
}
long start = System.nanoTime();
Node result = nodes2[i].reverse();
long end = System.nanoTime();
long diff2 = end - start;
double ratio = (double) diff2 / (double) diff;
assertTrue("reverse should scale linearly with list size", ratio > 1.2);
assertTrue("reverse should scale linearly with list size", ratio < 2.5);
}
我的代码生成的比率范围为 25 到 35，而它需要介于 1.2 到 2.5 之间。
最佳答案
由于您的代码似乎只迭代列表一次，因此实际上似乎是 O(n)。
但是，您在外观中分配对象(new Node())，因此实际性能将取决于内存分配(其中包括对大型数据集的操作系统调用)和垃圾收集。两者都需要不确定的时间。这意味着即使算法(理论上)是 O(n)，测量的运行时间也将取决于 n 之外的其他因素。
您应该尝试重写算法来更改现有节点的链接，而不是创建新节点。 (我假设作业是反转现有列表，而不是创建列表的反转副本)
关于java - 为什么这个在java中反转LinkedList的算法不适合θ(N)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42055352/