当我更改链表中的指针时，原来的指针是保持不变还是自动删除

Question

我有一个关于链表的基本问题

假设我反转以下链接列表：

#1->2->3->4变为4->3->2->1

假设我首先将指针从1反转到2；使得2比1。我的问题是，当我这样做时，从1到2的指针/连接是否仍然存在？

或者当我们执行2->1.

如果以上是真的；原始连接1->2->3->无论我们对指针做什么，4总是保持不变；或者它被删除了，如果说我把指针从1改为3；即1->3.则连接1->2会自动删除吗？

Answer 1

通常链表中的一个节点对另一个节点有一个引用：下一个节点。

当你有一个有4个节点的列表时，你可以这样可视化：

head
↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next: —————→ │ next: —————→ │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

你问：

假设我首先将指针从1反转到2；使得2比1。我的问题是，当我这样做时，从1到2的指针/连接是否仍然存在？

"反转指针"；并不是真正正确的表达方式。"；指针"；从1到2的点将设置为None，并且另一个参考将设置为从2到1的点。这不是同一个！

因此，首先，第一个节点中的next引用是指它之前的节点，但由于没有这样的节点，它变成了None:

head
↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│   │ next: —————→ │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

第二个节点也是如此。其next引用是指第一个节点：

head
↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

更多关于典型反转算法的信息

作为附加步骤，head参考应指向现在已经反转的零件的起点：

head
↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

在这个反转的每一步，next被改变的节点和最初跟随它的节点之间都会断开连接(在最后一次可视化中，值为3的节点不能再从左侧的节点到达(。

因此，您需要有一个变量来记住最初的下一个节点是什么，这样您就可以继续并更改该节点的next属性。您可以将该变量称为next:

head           next
↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

如果我们继续下一步，将执行以下操作：

我们复制next的参考。。。可能在一个名为current:的变量中

current
head           next
↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

然后通过用变量next:引用原始的下一个节点，记住它是什么

head           current        next
↓              ↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │   │ next: —————→ │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

然后将参考值从3更改为4，将参考值由3更改为2:

head           current        next
↓              ↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │ ←———— :next  │   │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

请注意，现在最右侧的节点已分离。我们仍然需要更新head参考：

head
current        next
↓              ↓
┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ data: 1  │   │ data: 2  │   │ data: 3  │   │ data: 4  │
│ next:None│ ←———— :next  │ ←———— :next  │   │ next:None│
└──────────┘   └──────────┘   └──────────┘   └──────────┘

现在只剩下一个循环，通过设置current参考开始。。。等

另请参阅此递归函数如何反转链表？