反向LinkedList

Question

下面给出了反向链表的两种代码，第一种是正确工作的，第二种则不是。有人能解释一下为什么会这样吗？

工作守则：

def rev(curr, prev):
    if not curr:
        return prev
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next
    return rev(curr, prev)

非工作守则：

def rev(curr, prev):
    if not curr:
        return prev
    # next = curr.next
    curr.next = prev
    # prev = curr
    # curr = next
    return rev(curr.next,curr)

我以这样的方式调用上述两种功能： 主任(无)

输入:

1->2->3->4->None

第一代码的输出:

4->3->2->1->None

第二代码的输出:

1->None

所需的第二个代码的输出:

4->3->2->1->None

Answer 1

在执行以下操作之后，您正在执行递归调用return rev(curr.next,curr)：

curr.next = prev

因此，在初始调用rev(head, None)中，您可以设置head.next = None，然后用None调用rev (并返回head)。

改为：

def rev(curr, prev):
    if not curr:
        return prev
    next = curr.next
    curr.next = prev
    return rev(next,curr)