递归链表反转在打印语句时卡住

Question

我正在写一个Python程序，目的是用递归的方法反转一个链表。我已经实现了反转的功能，并且加了一些打印语句来帮助我理解这个过程。不过，当我加上某些打印语句后，程序就会卡住，无法完成。没有那些打印语句的时候，反转功能似乎运行得很好。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        next = self.next
        val = self.val
        out = f"ListNode({val}, "
        count_paren = 1
        while next is not None:
            val = next.val
            out += f"ListNode({val}, "
            next = next.next
            count_paren += 1
        out += f"{next}"
        out += count_paren * ")"
        return out

def reverse(head):
    if not head or not head.next:
        return head
    print("1 HEAD", head)
    new_head = reverse(head.next)
    print("2 NEW_HEAD", new_head)
    head.next.next = head
    print("3 HEAD", head)
    print("4 NEW_HEAD", new_head)
    head.next = None
    print("5 HEAD", head)
    print("6 NEW_HEAD", new_head)
    return new_head

lst = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(lst)
print(reverse(lst))

没有打印语句的时候：

    print("3 HEAD", head)
    print("4 NEW_HEAD", new_head)

反转功能运行得很好。但是，如果我把那些打印语句取消注释，程序就会卡住。

我希望能得到一些关于为什么会这样，以及我该如何修改这些打印语句，以便更好地理解这个过程而不导致程序卡住的建议。我使用的Python版本是 3.11.2。

Answer 1

问题似乎出在你用"repr"函数打印语句的方式上。ListNode类的方法在递归调用自己，这样就导致了无限循环，所以程序就卡住了。

你可以试试下面的代码：

def __repr__(self, visited=None):
if visited is None:
    visited = set()
if self in visited:
    return "ListNode(...)"
visited.add(self)
next_node = self.next
val = self.val
out = f"ListNode({val}, "
if next_node is not None:
    out += next_node.__repr__(visited)
out += ")"
return out

Answer 2

问题在于你在反转链表的过程中使用了 print 语句。这个反转操作会暂时产生循环，如果在这种状态下调用 print，它又会调用 __repr__，这样就会陷入无限循环。

解决办法是，在反转链表的时候，不要用 print 来打印 节点（你已经发现了这一点），至少在链表暂时有循环的时候不要这样做。

这个暂时的循环是在你执行 head.next.next = head 时产生的，而在你执行 head.next = None 时又被打破。为了避免在你的 Python 代码中出现链表有循环的情况，建议使用元组赋值的方式：

head.next.next, head.next = head, None

Answer 3

问题在于你设置了 head.next.next = head，然后又用 print("3 HEAD", head) 或 print("4 NEW_HEAD", new_head) 调用了 __repr__。在 __repr__ 中，它会不断查找 .next 属性，但这会导致无限循环，因为经过两次迭代后，正在处理的节点是 head.next.next，而你已经把它设置成了 head 本身！在这个循环中，next 的值是这样的：

head -> head.next -> head.next.next (=head) -> head.next -> head.next.next (=head)

正如你所看到的，这就造成了一个循环，所以去掉打印语句就能解决这个问题。

其实你可以通过在函数早些时候“断开链条”来完全避免形成循环。一个方法是在函数开始时获取 head.next 的引用，然后我们可以安全地设置 head.next = None，这样就不会有无限循环的风险；如果你运行这个函数，你会发现我们可以在任何地方安全地调用 __repr__：

def reverse(head):
    if not head or not head.next:
        return head
    print(f"1 {head = }")
    head_next = head.next
    print(f"2 {head = }")
    head.next = None
    print(f"3 {head = }")
    new_head = reverse(head_next)
    print(f"4 {head = }\n{new_head = }")
    head_next.next = head
    print(f"5 {head = }\n{new_head = }")
    return new_head

另外，你可以通过让 __repr__ 函数变成递归的方式来简化它：

    def __repr__(self):
        return f"ListNode({self.val}, {self.next})"