linked-list - 使用具有随机指针的节点反转链表

Question

我最近遇到了这个有趣的问题:

“考虑一个带有每个节点的链表，除了有一个‘next’指针还有一个‘随机’指针。‘随机’指针指向链表上的一些随机的其他节点。它也可能指向NULL。到简化事情，没有两个“随机”指针会指向同一个节点，但超过 1 个节点的随机指针可以指向 NULL。

现在我们需要反转链表的所有指针(包括“next”和“random”)的方向。约束是解决方案必须是 O(1) 空间复杂度(可以创建恒定数量的新节点，但与列表的长度不成正比)”

我花了很多时间思考这个问题。我不太相信这实际上是可能的。

Answer 1

您还需要考虑随机链形成(简单)循环的情况。
您可以通过链的线性遍历来检测循环；如果循环中有偶数个节点，则必须再次处理重新反转。