递归反向链表

Question

我对在 Python 中递归反转链表的算法有疑问。

def reverse(lis, prev = None):
    if lis.next != None:
        reverse(lis.next, lis)
    lis.next = prev

输入： 3 1 4

输出： 3

知道为什么它不起作用吗？

Answer 1

问题是您的链表的根也发生了变化：更改列表后，您的元素3确实是最后一个元素，您的函数也最好返回根：

def reverse(lis, prev = None):
    if lis.next != None:
        temp = lis.next
        lis.next = prev
        return reverse(temp, lis)
    else:
        return lis # the new root

所以现在你用它来称呼它：

oldroot = ... #construct linked list
newroot = reverse(oldroot)
print(newroot)

所以你的函数是正确的，但是你操作后手上的链表元素是错误的。