给定一个节点如何在单链表中找到先前的节点 [英] given a node how can I find previous node in a singly linked list

问题描述

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

解决方案

你不能。

定义只将每个节点链接到其后继者，而不是前身。没有关于前辈的信息;甚至没有关于它是否存在的信息（您的节点可能是列表的头）。

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

您可以扫描整个堆寻找记录它看起来像一个指向节点的前导节点。 （不是一个严肃的建议。）

Given the current node, how can I find its previous node in a Singly Linked List. Thanks. Logic will do , code is appreciated. We all know given a root node one can do a sequential traverse , I want to know if there is a smarter way that avoids sequential access overhead. (assume there is no access to root node) Thanks.

解决方案

You can't.

Singly-linked lists by definition only link each node to its successor, not predecessor. There is no information about the predecessor; not even information about whether it exists at all (your node could be the head of the list).

You could use a doubly-linked list. You could try to rearrange everything so you have the predecessor passed in as a parameter in the first place.

You could scan the entire heap looking for a record that looks like a predecessor node with a pointer to your node. (Not a serious suggestion.)

这篇关于给定一个节点如何在单链表中找到先前的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！