给定一个节点，如何在单向链表中找到前一个节点 [英] 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.

推荐答案

你不能.

单链表根据定义只将每个节点链接到它的后继节点，而不是前驱节点.没有关于前任的信息；甚至根本没有关于它是否存在的信息(您的节点可能是列表的头部).

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屋！