有效地在双向链接列表中搜索具有指针约束的值？

debugcn 发表于 Dev

杰纳迪

我得到了这个问题来解决：

假设您获得了一个双向链接列表和一个指向该列表中某些元素的指针。假设您要在列表中搜索某个值v，您知道该值存在于某处。除p外不使用任何指针，设计一个用于查找v的Θ（m）时间算法，其中m是p与包含v的节点之间的距离。请勿修改输入列表。

有谁知道如何解决这个问题？我可以想到的唯一方法是破坏性地修改列表。

伯恩哈德·巴克（Bernhard Barker）

我认为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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。