时间戳

首页 > 解决方案 > 当我更改链表中的指针时，原始指针是否仍然保留或自动删除？

python - 当我更改链表中的指针时，原始指针是否仍然保留或自动删除？

问题描述

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

假设我反转了以下链表：

#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 会自动删除吗？

标签： pythonlinked-list

解决方案

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

当您有一个包含 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参考开始......等等。

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

推荐阅读