递归添加到有序链接列表中
递归添加到有序链接列表中
提问于 2017-10-24 06:33:28
我正在尝试创建一个add函数，以递归方式添加到有序链接列表中，但似乎无法开始。我得到了这两个函数
def add(self, item):
new_node = Node(item)
curr = self.__head
prev = None
self.add_recursive(new_node, curr, prev)
def add_recursive(self, new_node, curr, prev):
pass我知道如何在传统方法中添加有序链接列表，但我似乎无法理解如何通过这种方式调用它，以及使用递归。在这个类中可以使用的其他函数是.is_empty()和.size()。
谢谢
Stack Overflow用户
回答已采纳
发布于 2017-10-24 06:47:27
当涉及到层次结构(如树)时，人脑可以很容易地想象递归(我们认为递归)，但是对于像链表这样的平面结构，这显然很难做到。
让我们把这个拆开。在什么时候我们应该添加一个节点？当然，当我们知道curr前面没有节点的时候。此时，您将分配curr.next = new_node并返回。在此之前，先推进curr并继续。这也是在迭代意义上发生的事情。
将这一理解放入代码中，您就可以
def add_recursive(self, new_node, curr, prev):
""" note that we aren't yet taking care of the case when head is None """
if not curr.next:
curr.next = new_node
return
return self.add_recursive(new_node, cur.next, cur)一个重要的考虑因素是当你插入第一时间时的拐角情况。在这种情况下，您将调用.is_empty或size，并检查链接列表是否有任何元素，并相应地分配self.head = new_node
if self.is_empty():
self.head = new_node
return这是必须做的第一次检查。因此，您的全部功能现在变成：
def add_recursive(self, new_node, curr, prev):
if self.is_empty():
self.head = new_node
return
elif not curr.next:
curr.next = new_node
return
return self.add_recursive(new_node, cur.next, cur)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/46903638
复制相关文章
相似问题
腾讯云开发者
