使用递归反转单链表

Question

我做了一个函数，使用递归方法反转单向链表。 但是我在执行以下代码时遇到一些困难：

class node:
def __init__(self,data=None):
self.next=None
self.data=data
class linked_list:
def __init__(self):
self.head=node()
def append(self,data):
new_node=node(data)
cur_node=self.head
while (cur_node.next!=None):
cur_node=cur_node.next
cur_node.next=new_node
return cur_node.data
def display(self):
elements=[]
cur_node=self.head
while(cur_node.next!=None):
cur_node=cur_node.next
elements.append(cur_node.data)
print(elements)
def reverseRecursive(self,prev_code,cur_node):
if cur_node.next!=None:
reverseRecursive(cur_node,cur_node.next)
cur_node.next=prev_node
else:
self.head=cur_node
return
lst1=linked_list()
lst1.display()
lst1.append(1)
lst1.append(3)
lst1.append(5)
lst1.append(7)
lst1.display()
lst1.reverseRecursive(None,_____)
lst1.display()

我应该在反向递归函数/方法中传递第二个参数以便我可以执行它吗？

作为第二个参数，我想简单地传递链表的头节点。但是我不知道如何从类的init方法获取头节点linked_list

我已经尝试了几件事，但我无法解决它。也许我不太擅长OOP概念。任何人都可以帮助我解决这个问题吗？

Answer 1

链表是一种递归结构，因此将其与函数式风格一起使用将产生最佳结果。在您的程序中，您已经使用过程样式和可变节点实现了链表——随着时间的推移，您可以更改data和next的值。虽然这可能感觉像是一种直观的方法，但我想专注于一个不可变的学科，它将我们从严重的状态复杂性中解放出来。

首先，我们修复node构造函数。我们在构建新节点时设置了这两个属性，因为它们稍后不会在程序中更改 –

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

那么linked_list只是由特定约定构造的单个节点：

• node.data保留节点的数据
• node.next是：
  • 另一个linked_list
  • 或者，None，表示列表的末尾

我们从linked_list的构造函数开始 –

class linked_list:
def __init__ (self, node = None):
self.node = node
# ...

并实现is_empty、head和tail属性来抽象出node

class linked_list:
def __init__ (self, node = None):
self.node = node
@property
def is_empty (self):
return self.node is None
@property
def head (self):
if self.is_empty:
raise Exception ("cannot get head of an empty list")
else:
return self.node.data
@property
def tail (self):
if self.is_empty:
raise Exception ("cannot get tail of an empty list")
else:
return self.node.next

现在node的使用是完全抽象的，我们可以通过使用我们的新属性来编写更高级别的列表行为——

class linked_list:
... 
def length (self):
if self.is_empty:
return 0
else:
return 1 + self.tail.length()

在上面，我们看到通过使用其属性来谈论我们的列表非常容易。在我们继续之前，让我们看看如何使用print构建列表并可视化它们。对于对象到字符串的转换，我们使用__str__–

class linked_list:
... 
def add (self, x):
return linked_list (node (x, self))
def __str__ (self):
if self.is_empty:
return "None"
else:
return str (self.head) + " -> " + str (self.tail)
ls = linked_list().add('A').add('B').add('C')
print (ls)
# C -> B -> A -> None
print (ls.length())
# 3

请记住，因为我们构建了一个不可变的链表，add不会更改它被调用的列表 –

ls = linked_list().add('A').add('B').add('C')
print (ls)
# C -> B -> A -> None
print (ls.add('D'))
# D -> C -> B -> A -> None
print (ls)
# C -> B -> A -> None

最后，我们可以实施reverse——

class linked_list:
# ...
def reverse (self):
def loop (ls, acc):
if ls.is_empty:
return acc
else:
return loop (ls.tail, acc.add(ls.head))
return loop (self, linked_list())
ls = linked_list().add('A').add('B').add('C')
print (ls)
# C -> B -> A -> None
print (ls.reverse())
# A -> B -> C -> None

反转列表不会改变它

print (ls)
# C -> B -> A -> None
print (ls.reverse())
# A -> B -> C -> None
print (ls)
# C -> B -> A -> None