原来的链表变了

Question

一旦我尝试反转 link 列表的后半部分，主要变化中的原始 linked 列表就会发生变化，但我不明白具体是怎么做的。如果有人能给我一个详细的解释，我将不胜感激。我在代码中留下了一些注释，解释了我不确定发生了什么的地方。

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next



def is_palindromic_linked_list(head):  
  if head is None or head.next is None:
    return True

  # find middle of the LinkedList
  slow, fast = head, head
  while (fast is not None and fast.next is not None):
    slow = slow.next
    fast = fast.next.next

  '''
  Here I reverse the second half of the link list.

  The variable slow points to the second half of the link list and
  the reversed linked list is now head_second_half.
  
  If I print out each node, in link list head, every node prints out from the
  original link list on this line before the reversal.
  '''

  head_second_half = reverse(slow)  # reverse the second half
  # store the head of reversed part to revert back later

  '''
  Here although I am passing slow into the reverse function to reverse the second
  half of the link list my link list head gets modified and I can see this because
  by printing out all nodes from link list head on this line after the reversal I
  seem to only get the first half of the link list 
  '''

  copy_head_second_half = head_second_half

  # compare the first and the second half
  while (head is not None and head_second_half is not None):
    if head.value != head_second_half.value:
      break  # not a palindrome

    head = head.next
    head_second_half = head_second_half.next

  reverse(copy_head_second_half)  # revert the reverse of the second half
  
  if head is None or head_second_half is None:  # if both halves match
    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


def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(2)

  print("Is palindrome: " + str(is_palindromic_linked_list(head)))

  head.next.next.next.next.next = Node(2)
  print("Is palindrome: " + str(is_palindromic_linked_list(head)))


main()

我在上面有一些评论解释了我对正在发生的事情的理解存在的问题。我最初的想法是只拥有一个变量，该变量具有 link 列表的反向后半部分和代码的其余部分，而不恢复为 link 列表的原始顺序。这不起作用，因为当我在 main 中第二次调用 is_palindromic_linked_list(head) 时，link 列表已被修改并且没有属性 .next

根据我的理解，变量 slow 是一个指针，指向 link 列表后半部分开始的内存地址，因此，当我反转后半部分时linked 列表我原来的 linked 列表也被修改了吗？如果是这种情况，那么具体发生了什么，因为我无法理解如何恢复反转以某种方式保持原始 linked 列表在 main 中保持不变。我的意思是，在我的 main 函数中，如果我要从 link 列表头打印出每个节点，而不还原 is_palindromic_linked_list 函数中的反转 link 列表已更改，因此在某些时候不包含 .next 所以我第二次调用此函数时发生错误，但通过反转 linked 列表它可以工作。

我知道涉及到地址，但我不明白这里发生了什么，因为我在分离 linked 列表的后半部分时看到了它，所以无论我对此做什么 link 列表我认为会与原始列表完全分开，所以我的意思是通过分离它我可以看到我原来的 link 列表现在只包含前半部分并再次反转这个分离的 link列表（我认为现在与我原来的 linked 列表无关）以某种方式保留了我最初的 linked 列表。

我不确定我说得对不对。我正在努力解释我的思考过程，真的很想得到一些澄清。

Answer 1

when I reverse the second half of the linked list the my original linked list get modified as well?

是的，因为节点的 collection 是相同的：没有创建新节点，只是修改了（它们的 next 属性）。因此，当您在列表的后半部分修改节点时，这当然会影响列表。

它可以帮助可视化列表。让我们以一个包含值 1、2、3、4、5 和 6 的列表为例：

 head                                   slow
  ↓                                      ↓ 
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│value: 1 │  │value: 2 │  │value: 3 │  │value: 4 │  │value: 5 │  │value: 6 │  
│next: —————→│next: —————→│next: —————→│next: —————→│next: —————→│next:None│
└─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘

执行完head_second_half = reverse(slow)后，出现这种情况：

 head                                   slow                   head_second_half
  ↓                                      ↓                         ↓           
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│value: 1 │  │value: 2 │  │value: 3 │  │value: 4 │  │value: 5 │  │value: 6 │  
│next: —————→│next: —————→│next: —————→│next:None│←—————:next │←—————:next | 
└─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘

因此，如果现在您要迭代从 head 开始的列表，您将得到 1,2,3,4。从 head 开始，您无法再到达节点 5 和 6，因为 4 处的节点已成为尾节点，即它没有 next。显然它不能同时是下半场的尾巴，又是仍然与值为5的节点相连的节点。它只能处于一种状态。这就是它截断原始列表的方式。

通过第二次反转，您将列表恢复到其原始状态。

回想一下，在此过程中只有这 6 个节点。没有创建或复制其他节点。只有那6个存在。唯一发生的事情是使用了几个变量来引用某些节点，并且一些节点获得了不同的 next 值，但我们继续使用给定的 6 个节点。没有文案。

原来的链表变了

Original linked list changed

python

memory

linked-list