在 Python 中的单链表中的另一个节点之前插入一个节点？

Question

我确实看到了这个 post here [java] 并且正在尝试类似的解决方案，但是提到的线程没有完全回答我的问题）

我需要使用单链表并想尝试执行 insertBefore() 方法。我知道双向链表有一个 previous 属性，而单向链表没有，所以我知道使用双向链表可能会更好地实现这一点，但这是作业的要求，我正在努力解决问题。

到目前为止：我已经设置了我的节点 class 以及我的 SinglyLinkedList class。我还有我的 insertBefore() 方法，这是我的目标，也是我遇到困难的地方。

你会在我的 if 语句中看到，我希望将 node.next.value 与我的 targetNode 进行比较（注意 targetNode 是一个值）——为什么我的 node.next.value抛出以下错误？ if node.next.value == targetNode: AttributeError: 'NoneType' object has no attribute 'value'

# this is our node object
class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# this is our singly linked list object
class SinglyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def insertBefore(self, targetNode, value):
        # create new node
        newNode = Node(value)
        # find target node to insert
        node = self.head
        if node == None:
            print 'There aren\'t any nodes to insert before!'
        else:
            found = None
            # search nodes
            while node:
                if node.next.value == targetNode:
                    found = True
                    print node.value + ' <--this was node before target'
                    beforeInsert = node
                    afterInsert = node.next
                    beforeInsert.next = newNode
                    newNode.next = afterInsert # sets new node's next to target node
                    node = node.next # continues through while loop
                else:
                    node = node.next
            if found != True:
                print 'Your target node of {} was not found in the list!'.format(targetNode)

请注意：我能够使它适用于 insertAfter() 方法（未包含在上面的代码片段中），但我正在努力匹配 node.next 与 targetNode 对象。

Answer 1

正如您自己所建议的，问题似乎是您使用目标节点创建了一个新节点，node.next == Node(targetNode) 因为这永远不会成立。

我假设 targetNode 是一个 Node 对象，在这种情况下您应该简单地使用 node.next == targetNode。

你的代码的另一个问题是你没有检查第一个节点是否是目标节点。因此，您将无法使用 insertBefore 函数在头部 Node 之前插入节点。

以下代码是对 insertBefore 函数的重写，它在给定节点之前插入具有指定值的新节点。

def insertBefore(self, targetValue, value):
    # create new node
    newNode = Node(value)
    # find target node to insert
    node = self.head
    if node == None:
        print 'There aren\'t any nodes to insert before!'
    else:
        # search nodes
        if node.value == targetValue:
          newNode.next = self.head
          self.head = newNode

        while node.next is not None:
            if node.next.value == targetValue:
                print ">>> ",node.value,' <--this was node before target'
                newNode.next = node.next
                node.next = newNode
                return
            else:
                node = node.next
        print 'Your target node of {} was not found in the list!'.format(targetNode.value)

如果你想让targetNode成为目标节点的值，你需要比较node.next.value和targetNode。请注意，这会在目标值第一次出现之前插入该值。因此，您可能希望将您的列表变成一个集合。

Answer 2

以下是我如何找到我的问题的解决方案：

    def insertBefore(self, targetValue, value):
    # create new node
    newNode = Node(value)
    # find target node to insert
    node = self.head
    if node == None:
        print 'There aren\'t any nodes to insert before!'
    else:
        found = False
        # search nodes
        while node:
            if node.next == None:
                break
            if node.next.value == targetValue:
                found = True
                newNode.next = node.next
                node.next = newNode
                break
            else:
                node = node.next
        if found != True:
            print 'Your target node of {} was not found in the list!'.format(targetValue)

请注意，正如 Jonas 在他的评论中指出的那样，上述解决方案仅在节点列表中没有重复项时才有效。

在 Python 中的单链表中的另一个节点之前插入一个节点？

Insert a node before another node in singly linked list in Python?

python-2.7

singly-linked-list