反向链接列表

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。

更改为：

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