在Python中的單向鏈表中的另一個節點之前插入一個節點？

Question

我沒有看到這個帖子here【JAVA]和在嘗試類似的解決方案，但指出線程沒有完全回答我的問題）

我需要用單鏈表的工作，想嘗試和執行的insertBefore（ ） 方法。我知道雙鏈表有一個先前的屬性，而單鏈表沒有，所以我明白這可能會更好地使用雙鏈表完成，但這是作業的要求，我試圖解決的事情。

到目前爲止：我有我的Node類設置以及我的SinglyLinkedList類。我也有我的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

這裏是我如何能夠找到解決我的問題：

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) 

注意，約拿在他的評論中指出，上述方案只是如果在節點列表中沒有重複的工作。

Answer 2

正如你所建議的那樣，問題似乎是你使用目標節點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爲目標節點的值，則需要使用targetNode比較node.next.value。請注意，這會在第一次出現目標值之前插入值。因此，您可能想將列表變成一個集合。