algorithm - 有人可以向我解释给定头节点的双向链表的反转吗？

Question

我看过其他解决方案，但我很难想象效果。我知道我们必须切换 .next 和 .prev 但我不明白为什么我们要迭代到 .prev

举个例子:给定 Null--->A--><--B---><---C---><--D-->Null

如果头是A

我们设置一个变量“遍历”到head

while traverse != Null...

1) temp = traverse.prev

2) traverse.prev = traverse.next

3) traverse.next = temp

4)(混淆部分)** traverse = traverse.prev?

所以在我们给定的设置中，在第一次迭代之后它将是...

B--><--A-->空的，C---><--->D--->空的

鉴于此，如果遍历 B，我无法想象第二次及以后的迭代，我们最终会交换 C 和 A？

Answer 1

你已经交换了A的上一个/下一个，但是没有触及B，所以B一定还是

A<--B-->C

你将指向 b，所以我认为下一次迭代你将交换 b 的上一个/下一个指针，然后转到 c(在切换之后，它将是 b.prev)...我假设当你完成后，您将返回一个指向“遍历”的指针，这将是新的头 (D)。

请注意，在任何两次迭代之间，列表将被弄乱(无效)，因为在有效列表中，node.next.prev 必须是除最后一个对象之外的每个对象的节点，但在第一次迭代之后，A.next 将为空并且A.prev.prev 将是一个不正确的。

由于列表无效，您将无法再使用简单的 ascii 符号对其进行可视化，它假定 node.next.prev=node 始终成立。

一个有效的符号可能是:

初始:

Null<--A-->B  A<--B-->C  B<--C-->D  C<--D-->Null
       ^
     Traverse

第一次迭代后:

B<--A-->Null  A<--B-->C  B<--C-->D  C<--D-->Null
            ^     ^
            ^   Traverse
            ^
        Temporarily 
         invalid.

使用这个新符号，再试一次。

此外，我会将“While”条件移动到最后并使其成为:

While (traverse.prev != null)

这样你仍然持有一个指针来遍历指向新的头部(你可以返回给调用者)，否则你所拥有的只是一个指向尾部(原始头部)的指针，这现在不是很有趣.

哇，我在这个答案上付出了比我应该付出的更多的努力——但我喜欢数据结构。