为什么更改复制的链表版本会更改原始链表

Question

def is_palindromic_linked_list(head):
if head is None or head.next is None:
return True
slow = head
fast = head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
head_second_half = reverse(slow) #6, 4, 2 => 2, 4, 6
copy_head_second_half = head_second_half #<------HERE: copied linkedlist

while (head is not None and head_second_half is not None):
if head.value != head_second_half.value:
break
head = head.next
head_second_half = head_second_half.next
reverse(copy_head_second_half) #<---HERE: reversed the copied version of the linkedlist to set it back to how it was. 
if head is None or head_second_half is None:
return True
return False
def reverse(head):

prev = None
while (head is not None):
next = head.next
head.next  = prev
prev = head
head = next
return prev

这有什么意义？链表的工作方式是否与变量不同，因为更改复制的版本会更改原始版本？

Answer 1

当可变对象出现时，问题就开始了。在您的案例中，您引用了相同的对象，这意味着每个标签都指向相同的对象。关于这个话题有太多要说的，但我建议从这里开始阅读

Answer 2

当您直接将原始列表分配给副本列表时，您就是在引用它。

您需要使用copy((，这取决于您的列表是否有其他对象，您可能必须使用deepCopy((，链接中对此进行了解释。

示例用法：

• 浅拷贝

浅拷贝构建一个新的复合对象，然后(尽可能(在其中插入对中找到的对象的引用原件。

copy_head_second_half = head_second_half.copy() #<------HERE: copied linkedlist

• 深度复制

深度复制构建一个新的复合对象，然后递归地将原始对象中的对象的副本插入其中。

copy_head_second_half = head_second_half.deepCopy() #<------HERE: copied linkedlist

Answer 3

如前所述，copy_head_second_half变量获取对反向链表的头节点的引用。未复制任何节点。但请注意，列表已经被reverse突变了，所以即使你认为你在用这个赋值复制列表，也为时已晚：原始列表的突变已经发生了。

您需要这个copy_head_second_half变量，不是因为您需要整个列表的副本，而是因为当head_second_half将指向后面循环中的其他节点时，您需要保留对该头节点的引用。如果没有这个复制的引用，你就会失去第二个列表的起点！

的确，调用reverse会使原始列表发生突变，但这就是代码再次调用reverse的原因：这样一来，突变就会逆转，当函数返回时，列表将恢复到原始状态。

这实际上是一个很好的做法：您不为复制列表的一半而分配内存。