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

Question

节点和链表classes:

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)

无论我做什么我都无法让它工作我已经尝试在节点 class 中添加另一个反向（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。例如我的链表是：1->2->3。如果我输入：“ll.reverse(LnLs())”，那么我希望我的链接将更改为 3->2->1。起初我运行这段代码说“AttributeError: 'LnLs' object has no attribute '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

以下是一些问题：

在您的第一个代码块中，您在 class 中定义了两次 reverse，因此第二个定义覆盖了第一个。
第二个 reverse 方法调用 reverse。没有全局 reverse 函数，只有一个具有该名称的方法。
如果您更改 reverse 的“签名”以采用额外的链表参数，您还需要更改构造函数对 reverse 的调用，因为该调用当前未传递第二个参数。或者，您应该为第二个 reverse 方法考虑另一个名称。
即使您将 reverse 递归调用更正为像方法一样调用，您也没有链表来调用它。 t 是一个节点，不是一个链表，所以如果你写 t.reverse(h)，它会导致错误，因为 Node 实例没有 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)

说明

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

请注意，这对第一个列表具有破坏性，因此将此发生在列表的 copy 上可能会很好。这样调用者就不会对空列表感到不愉快。

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

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

这也意味着调用者需要捕获对copy_reverse的调用的return值。所以您的主要代码如下所示：

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

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

how to reverse a singly linked list recursively using another empty linked list?

python

linked-list

singly-linked-list

说明