为什么prev，curr，下一个反向链表问题的迭代解是必需的？
为什么prev，curr，下一个反向链表问题的迭代解是必需的？
提问于 2022-07-16 15:36:23
链表的经典输入问题:给定单链表的头，反转列表，并返回反向列表。
例如，输入: head = 1,2,3,4,5输出: 5,4,3,2,1
在python中，一个非常典型的解决方案是
def reverseList(self, head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev在我看来，以下几点也会“起作用”
def reverseList(self, head):
curr=head
while curr.next:
tmp=curr
curr=curr.next
curr.next=tmp
return curr其中，我只使用2(tmp，curr)而不是3(prev，curr，next)‘变量’(如果描述它们的名字不对，请纠正我)。我知道我没有考虑到链表的结尾不应该指向任何一个。然而，它不应该给出类似于建议的解决方案的结果吗？但是，我得到了第二个运行时错误吗？哪里出问题了？
回答 2
Stack Overflow用户
回答已采纳
发布于 2022-07-16 17:57:45
让我们看看在第二个代码版本中，值1、2和3的链接列表会发生什么。
在循环开始之前，我们有这样的情况：
head,
curr
↓
┌──────────┐ ┌──────────┐ ┌──────────┐
│ data: 1 │ │ data: 2 │ │ data: 3 │
│ next: ─────► │ next: ─────► │ next:None│
└──────────┘ └──────────┘ └──────────┘在第一次迭代之后，更新了一个next引用：
head curr
↓ ↓
┌──────────┐ ┌──────────┐ ┌──────────┐
│ data: 1 │ │ data: 2 │ │ data: 3 │
│ next: ─────► │ next: ─┐ │ │ next:None│
└──────────┘ └────────│─┘ └──────────┘
↑ ▲ │
tmp └──────────────┘这看起来已经不对了，因为我们已经失去了对第三个节点的引用，第三个节点已经无法到达。因此，一旦更新了next属性，所有完成反转的希望都会丢失。
但是还要注意在第二次迭代中，curr是如何在列表中返回的，因为它遵循更新的next引用。这不是应该发生的事。curr应该继续前进。然后，它将head的next属性设置为第二个节点，但是已经是这样了(这里没有反转！)因此，curr将无止境地绕着圈走。
替代方案
与第一个工作版本相比，在执行元组赋值时，可以少使用一个变量：
def reverseList(self, head):
curr = head
prev = None
while curr:
curr.next, prev, curr = prev, curr, curr.next
return prev要将其简化为一个变量(head)，可以使用递归解决方案：
def reverseList(self, head):
if not head or not head.next:
return head
head.next.next, head.next, head = head, None, self.reverseList(head.next)
return headStack Overflow用户
发布于 2022-07-16 16:04:08
list = [1,2,3,4,5]
list.reverse()
print(list) // [5, 4, 3, 2, 1]def reverseMyList(list):
listReversed = []
for i in list:
listReversed.insert(0, i)
return listReversed页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/73005493
复制相关文章
相似问题
腾讯云开发者
