给定节点如何在单链表中找到先前的节点

Question

给定当前节点,如何在单链接列表中找到其先前节点.谢谢.逻辑将做,代码表示赞赏.我们都知道给定一个根节点可以进行顺序遍历,我想知道是否有一种更智能的方法可以避免顺序访问开销.(假设没有访问根节点)谢谢.

Answer 1

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

Python代码：

def deleteNode(自身, 节点):

node.val = node.next.val

node.next = node.next.next

@删除链表中的节点

Answer 2

从头开始遍历列表，直到遇到一个节点，该节点的next链接指向您当前的节点。

但是如果你需要这样做，也许你一开始就不应该使用单向链表。

Answer 3

单向链表的唯一选择是线性搜索，如下所示（类似 Python 的伪代码）：

find_previous_node(list, node):
   current_node = list.first
   while(current_node.next != null):
       if(current_node.next == node):
          return current_node
       else:
          current_node = current_node.next
   return null

Answer 4

你不能.

根据定义,单链接列表仅将每个节点链接到其后继节点,而不是前导节点.没有关于前任的信息; 甚至没有关于它是否存在的信息(你的节点可能是列表的头部).

您可以使用双向链表.您可以尝试重新排列所有内容,这样您就可以将前一个作为参数传入.

您可以扫描整个堆,查找看起来像具有指向节点的指针的前置节点的记录.(不是一个严肃的建议.)