作为链表数据结构学习者,我正在练习Leetcode问题"反向链表",我有自己的解决方案,但不知道为什么是错误的,任何人都可以专家分享一些指导吗?真的很感激!
李特代码问题:
反转单向链表。
例:
输入:1->2->3->4->5->空
输出:5->4->3->2->1->空
我的代码:
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
prev = None
while head:
temp = head
temp.next = prev
head = head.next
prev = temp
return prev
但是,上述解决方案是错误的,但可以通过在"temp.next = prev"和"head = head.next"之间切换位置来纠正,如下所示:
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
prev = None
while head:
temp = head
head = head.next
temp.next = prev
prev = temp
return prev
对我来说,切换两个语句与否没有区别,它们为什么不同?
以下是循环开始前的参考资料:
prev --> None
head --> [something| *-]-> [something| *-]-> ...
temp = head
后:
prev --> None
head --> [something| *-]-> [something| *-]-> ...
^
|
temp ----+
temp.next = prev
后:
prev --> None
head --> [something| *-]-> None .... -> [something| *-]-> ...
^
|
temp ----+
您不再引用 head 后面的列表部分。head = head.next
只是将head
也设置为None
。 然后,prev
设置为现在截断的列表的头部。
你必须记住,在表面之下,我们正在处理指针和它们在内存中指向的空间。
对于第一个解决方案,head 无法将自身分配给 head.next,因为 temp.next 现在指向 None。您已经有效地将 head.next 重新分配给 null,方法是将 temp.next 分配给 null。
第二种解决方案通过首先重新分配 head.next 来解决此问题。这并不意味着温度会随着头部移动。Head 现在指向 head.next,而 temp 指向 head 的上一个节点(在它转到 head.next 之前(。
temp = head
使temp
引用与head
相同的对象
考虑到这一点,下一行temp.next = prev
实际上与head.next = prev
相同,因为它们再次引用代码中的同一对象。
此修复解决了这个问题,因为在影响head
引用的对象之前,您将head
引用的内容完全重新分配给不同的对象 - 特别是链表中的下一个对象。