给定一个节点，如何在单链表中找到前一个节点

Question

给定当前节点，我如何在单链表中找到它的前一个节点。谢谢。逻辑会做，代码表示赞赏。我们都知道给定一个根节点可以进行顺序遍历，我想知道是否有一种更聪明的方法可以避免顺序访问开销。 （假设无法访问根节点）谢谢。

原文由 David Prun 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

你不能。

根据定义，单链表仅将每个节点链接到其后继节点，而不是前任节点。没有关于前任的信息；甚至没有关于它是否存在的信息（您的节点可能是列表的头部）。

您可以使用双向链表。您可以尝试重新安排所有内容，以便首先将前任作为参数传入。

您可以扫描整个堆以查找看起来像带有指向您节点的指针的前任节点的记录。 （不是认真的建议。）

原文由 hemflit 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果要删除当前节点，也可以在不查找上一个节点的情况下执行此操作。

蟒蛇代码：

def deleteNode（自我，节点）：

 node.val = node.next.val

node.next = node.next.next

@删除链表中的节点

原文由 ayush_manglani 发布，翻译遵循 CC BY-SA 4.0 许可协议