日常编码问题：一次性从链表中删除第 k 个索引

一次性从链表中删除第 k 个索引

欢迎回来，还有一个问题需要解决！今天，我们正在处理链表及其元素删除。我们将讨论一下什么是链表，我们将创建一个链表，并了解如何从中删除元素。

在开始之前，通常的免责声明：

• 这些问题由精彩的时事通讯每日编码问题提供，您可以订阅这里。看看吧，并尝试解决你的挑战！

• 我不是一个专业的程序员：只是一个喜欢分享他的镜头的人！如果您有更好或更快的算法解决方案，请在评论中提交！我很想了解更多相关信息！

  
  

废话不多说；让我们开始讨论问题吧！

这个问题最初是亚马逊提出的

给定一个链表和一个整数k ，从链表末尾删除第 k 个节点并返回链表的头。

k保证小于列表的长度。

一次性完成此操作。

好吧，让我们解释一下这里发生的事情：我们得到一个链接列表和一个要从列表中删除的索引元素k 。之后，我们应该返回链表的头。

最后，我们必须一次性完成所有这些操作，这意味着我们不能多次循环列表。

我们还保证索引k包含在列表中，因此我们不必检查它是否超出列表的实际长度。

今天我们将使用 Go 来构建算法，因为它的语法非常适合此类工作，同时它仍然非常易于理解。

让我们从头开始：构建一个简单的链表。

链接列表

链表背后的概念非常简单：它是一个由对象（通常称为节点）组成的列表，每个节点必须至少有两个属性：一个值（该节点实际包含的东西）和一个到下一个节点的链接。

通常，指针用作从一个节点跳转到另一个节点的链接。

另外，列表的第一个节点通常称为列表的头，这也是问题要求我们返回的节点。

这是一个图形示例：

左边的第一个节点是链表的头，它包含它的值 v₀ 和一个内存指针P(n₁) ，它将链表重定向到下一个节点n₁。接下来的节点n₁将包含其值和指向下一个节点的指针P(n2) ，依此类推。

当然，最后一个节点没有任何可指向的内容，因此其指针的值为null 。

让我们看看创建一个的代码！

代码非常简单：我们创建两种结构，一种用于内部节点，一种用于链表。

• 正如我们刚刚看到的，该节点将具有两个属性，即属性Value和属性Next ，后者保存*Node类型作为指向下一个节点的指针。

• 链表，一种“初始化”链表的结构，它只有一个属性，即链表的Head 。

  
  

之后，我们只需在主函数中初始化列表并为其头赋予一个随机值为 10 的节点。

理解链表背后的关键是，现在Head节点（由于其类型为Node ）本质上将具有Next属性，该属性Head包含下一个节点。然后，最后一个节点将具有其Next属性来跳转到下一个节点，依此类推。

一旦我们向列表中添加一些节点，一切都会变得更加清晰，所以让我们开始吧！我们有两个选择：要么手动完成，这是一项非常乏味的工作，要么为链表类编写一个方法来添加更多节点。让我们来看看！

添加节点：变相的可变列表

即使您几乎没有编程经验，在几乎每种编程语言中，您应该听说的第一个概念就是可变列表和不可变列表之间的区别。

顾名思义，可变列表是您可以操作并向其添加元素的列表。相反，不可变元素具有固定的大小，并且不能添加新元素。但为什么会这样呢？

不可变列表在内存中是连续的，这意味着它们的元素按顺序存储在内存中：对于 3 个元素的列表，如果第一个元素存储在 0x00，那么第二个元素将存储在 0x01，最后一个元素将存储在 0x02。

这就是为什么在 Python 中迭代固定数组、不可变列表或元组是如此之快，因为 CPU 只是一一回忆内存索引。

另一方面，可变列表仅在首次初始化时在内存中是连续的：此时，如果添加元素，它们将不再是连续的。那么我们如何循环它们呢？

嗯，因为第一个启动的最后一个元素将有一个指针，该元素在其后面添加，这将为我们带来附加的 to 元素，依此类推。所以，是的，可变列表实际上通常是变相的链接列表！

现在，让我们看一下代码：

我们将方法AddNode添加到链表的方法中。添加节点的过程如下：

• 首先，我们将Head值存储在名为current的变量中

• 接下来，我们循环链表，每次用下一个节点更新current变量，直到下一个节点为空。一旦我们当前所在的节点有一个空指针，我们就知道我们位于链表的最后一个节点。

• 最后，我们用一个新节点和一个新值更新最后一个节点（如果我们将其留空，则该新节点的Next指针将设置为 null）

  
  

从图形上看，这个过程是这样的：

我们可以在主函数中检查该方法的正确功能，打印出链表中节点的值。

删除节点

现在是我们问题的最后一部分和解决方案：删除具有正确索引的节点。首先，从链表中删除节点是什么意思？如果我们想一想，链表中的节点只有与前一个节点相连才存在，对吧？

例如，如果我们给 n-1ᵗʰ 的Next值为 null，我们可以将 nᵗʰ 值从列表中断开。

如果我们要删除的元素不是最后一个怎么办？好吧，我们可以通过将前一个元素连接到下一个元素来取消链接该元素！

因此，要删除 kᵗʰ 元素，我们必须找到 k-1ᵗʰ 元素并将其链接到 k+1ᵗʰ 节点。我们需要存储前一个节点 (k-1ᵗʰ) 。

显然，我们不能直接索引列表：尝试像linkedlist[n]这样的东西只会引发错误。不过，考虑到这一点，我们可以将列表的头视为索引 0，将其下一个节点视为索引 1，依此类推，并且我们也可以像之前所做的那样循环遍历节点。

然后我们可以做的是实现一个计数器来跟踪我们所在的节点！

那我们就来编码一下吧。

让我们看一下接受index属性的RemoveNode函数。之后，我们初始化三个变量：

• previousNode ，它将保存前一个节点

• current ，它将保存我们在循环期间所在的节点

• counter ，最初等于 0，这将保持我们在列表中的位置

  
  

让我们暂时跳过第一个 if 块，专注于 for 循环。我们开始循环，直到counter变量严格小于index ：然后每个循环将用当前节点更新前一个节点，然后继续更新当前节点和计数器。

当循环中断时，这意味着我们正好位于所需索引之前的节点上：我们只需使用我们所在的列表中的下一个节点来更新前一个节点prev.Next指针，即将是current.Next 。最后，我们返回链表的头。

现在，如果要删除的索引是索引为 0 的头，会发生什么情况？循环永远不会启动，因为它将以counter = 0和index = 0开始，并且条件将立即为 false。我们可以使用顶部的 if 块来管理第一种情况。

基本上，如果索引为0，我们可以直接用它旁边的节点更新链表的头，然后返回它。我想提醒您注意，特别是第 31 行：Go 与许多其他语言一样，通过 value 将属性传递给函数，这意味着该函数保留所传递对象的副本，而不是您传递的实际对象。

这个概念在这个例子中清晰可见：

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

我们创建一个函数来打印作为属性传递的值的内存地址。然后，在主函数中，我们创建一个变量 a 并打印出它的内存地址。然后我们将相同的变量传递给函数并打印它的内存地址。

正如您所看到的，如果您尝试，结果将会有所不同：这是因为属性作为值传递给函数，这意味着创建a的副本只是为了将其传递给函数。

回到我们的链表，对于上面同样的问题，我们必须使用指针来获取真正的头。因此，为了到达“真正的” ll.Node ，我们必须调用它的指针*ll.Node并使用*ll.Node = *ll.Node.Next将其进一步移动。

在 main 函数中，我们添加对该方法的调用，例如调用ll.RemoveNode(0)和ll.RemoveNode(2) ，我们可以检查结果中缺少节点 0 和节点 2 的情况。

结论

我们已经走到了最后！

如果你读到这里，我的全部感激之情都归于你。如果您愿意留下一两个赞并分享这篇文章，这会让我很高兴并帮助我继续写这些文章！

下一篇文章见，一如既往，感谢您的阅读。

尼古拉