麻烦为链表类实现递归Add方法

Question

我需要递归地为链接列表类实现add方法。我无法使我的代码正常工作。这是我到目前为止的内容：

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, val, current_node=0):

        if current_node == 0:
            current_node = self.head

        if current_node is None:
            current_node = Node(val)
        else:
            self.add(self, val, current_node.next)

此实现在哪里出错？

Answer 1

这是递归的滥用。这意味着，如果链接列表的长度大于调用堆栈可以容纳的长度，则该类将无故中断。递归编写也不太直观，所以这是一个输球。

话虽如此，教授通常会强迫您以递归方式进行操作，而这不应以递归方式进行。一起玩，我会写一个内部助手来处理实际的递归。这避免了笨拙的默认参数，该参数可能会使调用者感到困惑，并使他们无法打破函数的约定。

def add(self, val):
    def add_recursively(curr, prev):
        if curr:
            add_recursively(curr.next, curr)
        else:
            if prev:
                prev.next = Node(val)
            else:
                self.head = Node(val)

    add_recursively(self.head, None)

原始尝试的一个问题是：

if current_node is None:
    current_node = Node(val)

没有先前的Node引用，current_node实际上没有附加到任何东西，因此它在函数返回时只会被垃圾回收。

如果允许使用迭代，则更好：

def add(self, val):
    curr = self.head
    prev = None

    while curr:
        prev, curr = curr, curr.next

    if prev:
        prev.next = Node(val)
    else:
        self.head = Node(val)