如何使用另一个空链表递归地反转单个链表？

Question

节点和链接列表类：

class Node:
    def __init__(self, elm, nxt):
        self.elm = elm
        self.nxt = nxt
    
class LnLs:
    def __init__(self, s = None):
        self.head = None
        if s:
            for x in s:
                self.push(x)
            self.reverse()
            
    def __bool__(self):
        return self.head is not None

    def top(self):
        if not self:
            raise IndexError
        return self.head.elm

    def push(self, x):
        self.head = Node(x, self.head)

    def pop(self):
        x = self.top()
        self.head = self.head.nxt 
        return x

    def __iter__(self):
        p = self.head
        while p:
            yield p.elm
            p = p.nxt

    def index_of(self, x):
        for i, y in enumerate(self):
            if x == y:
                return i
        return -1

    def __getitem__(self, i):
        for j, x in enumerate(self):
            if i == j:
                return x
        raise IndexError

    def reverse(self):
        q, p = None, self.head
        # q points to the previous node
        while p:
            t = p.nxt
            p.nxt = q
            q = p
            p = t
        self.head = q
        
    def reverse(h, q):
        if h.head is None:
            return q
        else:
            t = h.head.nxt
            h.head.nxt = q
            return reverse(t, h)

无论我做什么，我都无法让它工作，我已经尝试在Node类中添加另一个反转（h，q）。 我已经尝试了至少5个小时，任何帮助都将不胜感激！ 这实际上是我的作业，我有去年同样问题的答案，那就是

def reverse(h, q):
    if h is None:
        return q
    else:
        t = h.nxt
        h.nxt = q
    return reverse(t, h)

EDIT1：很抱歉问问题的技巧很差。这是我第一次在这里提问。我试图使用此函数使用另一个空链表q反转链表h。e、 g.我的链接列表是：1->；2->；3.如果我输入：“ll.reverse（LnLs（））”，那么我希望我的链接将更改为3->；2->；1.首先我运行这段代码，它说“AttributeError:'LnLs'对象没有属性'nxt'”。然后我将代码更改为：

def reverse(h, q):
        if h.head is None:
            return q
        else:
            t = h.head.nxt
            h.head.nxt = q
            return reverse(t, h)

现在它显示NameError:name“reverse”未定义。如果我以另一种缩进的形式添加此函数（对不起，我不知道这在Python中叫什么，我将使用图片作为示例）：

然后我运行测试代码，现在我的链接只有一个元素：

if __name__ == '__main__':
    ll = LnLs()
    ll.push('apple')
    ll.push('orange')
    ll.push('peach')
    for x in ll:
        print(x)
    ll.reverse(LnLs())
    for x in ll:
        print(x)

输出： 桃 橙色 苹果 桃子

这就是我感到困惑的地方，因为我不知道我还能做什么。再次感谢

Answer 1

以下是一些问题：

• 在第一个代码块中，您在类中定义了reverse两次，因此第二个定义覆盖了第一个定义

• 第二个reverse方法调用reverse。没有全局reverse函数，只有具有该名称的方法

• 如果更改reverse的“签名”以获取额外的链表参数，则还需要更改构造函数对reverse的调用，因为该调用当前未传递第二个参数。或者，您应该为第二个reverse方法想出另一个名称

• 即使将reverse递归调用更正为像方法一样调用，也没有可调用的链表t是一个节点，而不是一个链表，因此如果您要写入t.reverse(h)，则会导致错误，因为节点实例没有reverse方法。事实上，在您想要进行reverse递归调用时，您没有进行调用所需的两个链表

因此，我建议以不同的方式调用新方法，copy_reverse：

    def copy_reverse(self, other=None):
        if other is None:   # in case the argument was not provided
            # ...make a copy of the list so the original will not be destroyed,
            # ...and pass an empty linked list as argument 
            return LnLs(iter(self)).copy_reverse(LnLs())
        if not self:
            return other
        other.push(self.pop())
        return self.copy_reverse(other)

解释

此函数的思想是从第一个列表中弹出每个元素并将其推送到第二个列表。最后，第一个列表将为空，第二个列表将具有反向列表

请注意，这对第一个列表是破坏性的，因此最好将这种情况发生在列表的副本上。这样一来，打电话的人就不会对空名单感到不快的惊讶

因此，我们首先检查第二个参数是否与给定的一样（它默认为None）。如果没有，那么我们复制当前链表（使用iter，它调用__iter__方法），并再次调用函数，但这次是在副本上，并提供第二个参数

然后我们从列表中提取第一个元素，并将其推送到第二个列表（在前面）。这将通过递归调用重复，直到第一个列表为空。返回结果

这也意味着调用方需要捕获对copy_reverse的调用的返回值。因此，您的主要代码如下所示：

ll = LnLs()
ll.push('apple')
ll.push('orange')
ll.push('peach')
for x in ll:
    print(x)
result = ll.copy_reverse()  # <  changed
for x in ll:
    print(x)

或简称：

ll = LnLs(['apple', 'orange', 'peach'])
print(list(ll))
result = ll.copy_reverse()
print(list(result))