使用递归反转单链表

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

我应该在 reverseRecursive function/method 中传递第二个参数什么才能执行它？

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

我已经尝试了几件事，但我无法解决它。也许我不太擅长 OOP 概念。谁能帮我解决这个问题？

Answer 1

链表是一个递归结构，以函数式的方式使用会得到最好的结果。在您的程序中，您已经使用程序样式和 mutable 节点实现了一个链表——随着时间的推移更改 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 properties抽象掉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

使用递归反转单链表

Reversing Single Linked list using Recursion

python

oop

recursion

reverse

linked-list