Python中的單向鏈表反轉

Question

我想在python中創建一個簡單的單鏈表。 （我知道有沒有必要實施在Python列表，但是這不是重點）

這裏是我的代碼：

class Node: 
    def __init__(self,data): 
     self.data = data 
     self.next= None 



class List: 
    def __init__(self): 
     self.firstNode = Node(None) 

    def inserthead(self,newnode): 
     if not self.firstNode.next: 
      newnode.next = None 
      self.firstNode.next = newnode 
     else: 
      newnode.next = self.firstNode.next 
      self.firstNode.next= newnode 


    def __show(self,start): 
     if start.next: 
      print start.data 
      self.__show(start.next) 

    def printlist(self): 
     self.__show(self.firstNode) 

    def __reverte_recursive(self,node): 
     temp = None 
     if not node.next: return node 
     else: 
      temp = self.__reverte_recursive(node.next) 
      node.next.next= node 
      node.next = None 
     return temp 

    def reverte_list1(self): 
     self.firstNode=self.__reverte_recursive(self.firstNode) 

    def __reverte_iterative(self,node): 
     temp = None 
     previous = None 
     while node and node.next: 
      temp = node.next 
      node.next= previous 
      previous = node 
      node = temp 
     return previous 
    def reverte_iterative(self): 
     self.firstNode=self.__reverte_iterative(self.firstNode) 

nodeA = Node("A") 
nodeB = Node("B") 
nodeC = Node("C") 
nodeD = Node("D") 
nodeE = Node("E") 


list1= List() 

list1.inserthead(nodeA) 
list1.inserthead(nodeB) 
          class Node: 
    def __init__(self,data): 
     self.data = data 
     self.next= None 



class List: 
    def __init__(self): 
     self.firstNode = Node(None) 

    def inserthead(self,newnode): 
     if not self.firstNode.next: 
      newnode.next = None 
      self.firstNode.next = newnode 
     else: 
      newnode.next = self.firstNode.next 
      self.firstNode.next= newnode 


    def __show(self,start): 
     if start.next: 
      print start.data 
      self.__show(start.next) 

    def printlist(self): 
     self.__show(self.firstNode) 

    def __reverte_recursive(self,node): 
     temp = None 
     if not node.next: return node 
     else: 
      temp = self.__reverte_recursive(node.next) 
      node.next.next= node 
      node.next = None 
     return temp 

    def reverte_list1(self): 
     self.firstNode=self.__reverte_recursive(self.firstNode) 

    def __reverte_iterative(self,node): 
     temp = None 
     previous = None 
     while node and node.next: 
      temp = node.next 
      node.next= previous 
      previous = node 
      node = temp 
     return previous 
    def reverte_iterative(self): 
     self.firstNode=self.__reverte_iterative(self.firstNode) 

nodeA = Node("A") 
nodeB = Node("B") 
nodeC = Node("C") 
nodeD = Node("D") 
nodeE = Node("E") 


list1= List() 

list1.inserthead(nodeA) 
list1.inserthead(nodeB) 
list1.inserthead(nodeC) 
list1.inserthead(nodeD) 
list1.inserthead(nodeE) 


print "list" 
list1.printlist() 
print "list reverse" 
list1.reverte_list1() 
list1.printlist() 
list1.reverte_iterative() 
print "list reverse reverse" 
list1.printlist() 

，並有結果：

None 
E 
D 
C 
B 
list reverse 
A 
B 
C 
D 
E 
list reverse reverse 
E 
D 
C 
B 

爲某些原因我不能打印所有列表，並在第一種情況下不打印「A」節點 但打印第一個節點（但我檢查和B節點指向A） 第一個反向是好的 但這個rd再次不打印A節點，即使它是由B節點指向的。 打印的問題可能在__show函數中。 但我想我是一個概念性的錯誤。

感謝

Answer 1

def __show(self,start): 
    if start.next: 
     print start.data 
     self.__show(start.next) 

，僅顯示當前節點，如果有下一個節點，這就是爲什麼從不打印的最後一個節點。 應該是：

def __show(self,start): 
    if start: 
     print start.data 
     self.__show(start.next) 

你做檢查的類似的錯誤/分配節點，而不是它的旁邊，反之亦然整個代碼（inserthead()例如 - 這是造成正在打印的None）