python-3.x - 需要帮助理解带有递归的链表(Python)
问题描述
我正在处理一个处理链接列表和节点的项目,并且我正在努力知道到目前为止什么不起作用。当我运行这段代码时,我得到的只是 19。任何我不理解的解释都将不胜感激。
class Node:
"""
Represents a node in a linked list
"""
def __init__(self, data):
self._data = data
self._next = None
def get_data(self):
return self._data
def set_data(self, newData):
self._data = newData
def get_next(self):
return self._next
def set_next(self, newNode):
self._next = newNode
class LinkedList:
"""
A linked list implementation of the List ADT
"""
def __init__(self):
self._head = None
def get_head(self):
"""
Returns head of node
"""
return self._head
def rec_add(self, val, a_node):
"""
A recursive method that adds a value to the linked list
"""
# works for an empty list OR because it is recursive; will add the value when it reaches end of the list
if a_node is None:
self._head = Node(val)
return self._head
else:
self._head.set_next(self.rec_add(val, a_node.get_next()))
return self._head
def add(self, val):
"""
Helper method for recursive add method
"""
self._head = self.rec_add(val, self._head)
def rec_display(self, a_node):
"""recursive display method"""
if a_node is None:
return
print(a_node.get_data(), end=" ")
self.rec_display(a_node.get_next())
def display(self):
"""recursive display helper method"""
self.rec_display(self.get_head())
这就是我正在测试的内容,只有 19 个返回:
my_list = LinkedList()
my_list.add(13)
my_list.add(8)
my_list.add(19)
my_list.display()
解决方案
如果您的意图是将新节点添加到链表的末尾,那么您不希望self._head
每次添加新节点时都进行重置:
def add(self, val):
"""
Helper method for recursive add method
"""
self._head = self.rec_add(val, self._head)
通过这样做,您的代码会使下一个节点添加新的头节点,并且与前一个头节点的链接丢失。
相反,您想分配一次头部,遍历链表直到到达末尾,然后将新节点添加到列表中的最后一个节点:
def rec_add(self, val, a_node):
# works for an empty list OR because it is recursive; will add the value when it reaches end of the list
if a_node.get_next() is None:
a_node.set_next(Node(val))
return
else:
self.rec_add(val, a_node.get_next())
return
def add(self, val):
if self._head is None:
self._head = Node(val)
else:
self.rec_add(val, self._head)
推荐阅读
- python - Pyplot:鼠标悬停时显示标签值
- c# - 如何将比较逻辑实现到数组的集合属性中
- bash - 剪切命令以获取每行中的倒数第二个单词 | 重击
- python - Django Rest Framework - 序列化程序不保存具有 ImageField 的模型
- docker - GCP Cloud Run 上的 Logstash Docker:无法从网络接口找到可用的硬件地址
- html - 当 portsize 变小时,想要将导航栏从主节点的一侧推到主节点的顶部
- regex - 简单小数的正则表达式
- r.net - RDotNet 空引用异常
- python - 是否有一个简单的算法来检测每个范围的起始字符和结束字符?
- com - COM 对象与现有的“另存为”和“打开”窗口进行交互