使用指针约束高效地搜索双向链表中的值？

Question

我被赋予了解决这个问题的任务：

假设你有一个双向链表和指向该列表某个元素的指针。假设你想要查找列表中的某个值v，而你知道它在某个地方存在。使用除p以外的任何指针，设计一个Θ(m)时间复杂度的算法来查找v，其中m是p和包含v的节点之间的距离。不要修改输入列表。

有人有什么想法来解决这个问题吗？我唯一能想到的方法会破坏性地修改列表。

- Genadi

---

@Dukeling 你能具体说明一下吗？它怎么会很简单呢？ - Filipe Gonçalves

@FilipeGonçalves 已添加了一个答案。 - Bernhard Barker

Answer 1

作为提示：如果你向前走一步，退后两步，再向前走四步，再退八步等等，会发生什么？需要多少步才能找到元素？

在分析的过程中，把一个几何级数相加可能会很有用。如果有帮助的话，1+r+r²+r³+...+r^n-1=(rⁿ-1)/(r-1)。

希望这些信息对你有帮助！

- templatetypedef

---

我如何使用一个指针同时向前和向后移动？ - Genadi

谢谢，我考虑过这个问题，但我认为在最坏情况下它会占用m^2的空间（等差数列），因为你必须前进一步，后退两步，前进三步，后退四步等等，不完全如你所描述的那样。 - Genadi

@Genadi 如果你使用等差数列（向前一步，向后两步，向前三步，向后四步等），那么你是正确的，它需要m^2的时间。然而，尝试使用等比数列：2^0向前，2^1向后，2^2向前，2^3向后，2^4向前等等，看看会发生什么。 - templatetypedef

@Genadi 噢，澄清一下 - 当你前后移动时，你要查看遇到的所有节点的值。 - templatetypedef

@FilipeGonçalves 这个复杂度是O(m)。可以这样想——在任何方向上，你最多走m步（因为你每次都要将距离加倍，并在找到所需数字时停止）。那么总步数就是4m + 2m + m + m / 2 + m / 4 + m / 8 + ...，这个值的上限是m(4 + 2 + 1 + 1/2 + 1/4 + 1/8 + ...)。第二项收敛于8。 - templatetypedef

Answer 2

我认为templatetypedef给出了正确答案，但基于问题的原始措辞，下面的解决方案也浮现在脑海中。问题陈述说列表不能被“销毁或洗牌”，这可能意味着如果你能再次将其更改回来，则修改它是可以的 - 即使这不是真的，我仍然认为这是一种有趣的方法。

---

这个问题很容易用2个指针解决，一个向前走，一个向后走，同时移动直到找到所需值。

现在这很好，但我们只允许使用1个指针。

如果你考虑双向链表，我们知道前一个节点的next指针只是当前元素的指针，因此，如果我们失去了它，我们可以重新设置它。

所以，我们可以使用p.prev.next作为自由存储器（并且给定类似的参数，p.prev.prev.next也是如此）。

因此，我们只能使用一个向前的指针，并将向后的指针存储在p.prev.next中，随着我们的移动适当地移动它。

以下是一些Java风格的伪代码，忽略了列表末尾检查和简单的未找到它（我认为它已经足够复杂了）：

if p.data == v
  return v

p = p.next
p.prev.next = p.prev.prev

while not found
  if p == v || p.prev.next == v
    p.prev.next = p                   // restore p.prev.next
    return v
  p = p.next
  p.prev.next = p.prev.prev.next.prev // set up p.prev.next from p.prev.prev.next
  p.prev.prev.next = p.prev           // restore p.prev.prev.next

- Bernhard Barker

---

感谢@Dukeling！那是一个有创意的解决方案！ - Genadi

令人惊叹。太美妙了。虽然我会选择@templatetypedef的答案作为被采纳的答案，但这个回答非常聪明，绝对是天才之作。 - Filipe Gonçalves