使用递归反转单链表

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()

我应该如何在ReverseCursive函数/方法中传递第二个参数，以便执行它？

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

我试了几件事，但都解决不了。也许我不太擅长OOP概念。有人能帮我解决这个问题吗？

Answer 1

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

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

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

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

• 节点。数据保留节点的数据

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

class linked_list:
  def __init__ (self, node = None):
    self.node = 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

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

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

最后，我们可以实现反向——

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