反向单向链表(不知道为什么我的代码是错误的)



作为链表数据结构学习者,我正在练习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引用的内容完全重新分配给不同的对象 - 特别是链表中的下一个对象。

相关内容

  • 没有找到相关文章

最新更新