我正在尝试编写一个简单的函数来反转 Python 中的链表:
def reverse(head):
prev = None
nxt = head.next
head.next = prev
while nxt:
prev = head
head = nxt
head.next = prev
nxt = nxt.next
return head
仔细想想,逻辑似乎不错: 首先将 prev 移动到 head,然后将 head 向前移动,使其指向与 nxt 相同的节点,然后将 head.next 设置为原来的位置。终于把nxt向前推进了一位。迭代直到 nxt 到达列表末尾。
但是,当我尝试使用以下代码反转链表 0->1->2->3->4->5 时:
def traverse(head):
while head:
print(head.val)
head = head.next
它无休止地重复打印0和1。
最佳答案
正如 Michael 指出的,您的代码使链表中的第一个和第二个元素彼此指向。
修复非常简单,这就是我所做的:
def reverse(head):
nxt = head.next
head.next = None
while nxt:
temp1 = nxt.next
temp2 = head
head = nxt
nxt.next = temp2
nxt = temp1
此代码最初与您的代码执行相同的操作。然而,while 循环使用 2 个临时变量 temp1
和 temp2
来保存 nxt
周围变量的地址(两侧)。这可以防止代码中发生冲突。
希望这有帮助! 干杯!
关于python - 链表反转算法不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/73267628/