一次性从链表中删除第 k 个索引 欢迎回来，还有一个问题需要解决！今天，我们正在处理链表及其元素删除。我们将讨论一下什么是链表，我们将创建一个链表，并了解如何从中删除元素。 在开始之前，通常的免责声明： 这些问题由精彩的时事通讯每日编码问题提供，您可以订阅 。看看吧，并尝试解决你的挑战！ 这里 我不是一个专业的程序员：只是一个喜欢分享他的镜头的人！如果您有更好或更快的算法解决方案，请在评论中提交！我很想了解更多相关信息！ 废话不多说；让我们开始讨论问题吧！ 这个问题最初是亚马逊提出的  ，从链表末尾删除第 k 个节点并返回链表的头。 给定一个链表和一个整数 k   保证小于列表的长度。 k 一次性完成此操作。 好吧，让我们解释一下这里发生的事情：我们得到一个链接列表和一个要从列表中删除的索引元素  。之后，我们应该返回链表的头。 k 最后，我们必须一次性完成所有这些操作，这意味着我们不能多次循环列表。 我们还保证索引 在列表中，因此我们不必检查它是否超出列表的实际长度。 k 包含 今天我们将使用 Go 来构建算法，因为它的语法非常适合此类工作，同时它仍然非常易于理解。 让我们从头开始：构建一个简单的链表。 链接列表 链表背后的概念非常简单：它是一个由对象（通常称为 ）组成的列表，每个节点必须至少有两个属性：一个 （该节点实际包含的东西）和一个到下一个节点的 。 节点 值 链接 通常， 用作从一个节点跳转到另一个节点的链接。 指针 另外，列表的第一个节点通常称为列表的 ，这也是问题要求我们返回的节点。 头 这是一个图形示例：  左边的第一个节点是链表的头，它包含它的值 v₀ 和一个内存指针  ，它将链表重定向到下一个节点 接下来的节点 将包含其值和指向下一个节点的指针  ，依此类推。 P(n₁) n₁。 n₁ P(n2) 当然，最后一个节点没有任何可指向的内容，因此其指针的值为  。 null 让我们看看创建一个的代码！   https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true 代码非常简单：我们创建两种结构，一种用于内部节点，一种用于链表。 正如我们刚刚看到的，该节点将具有两个属性，即属性 和属性  ，后者保存 类型作为指向下一个节点的指针。 Value Next *Node 链表，一种“初始化”链表的结构，它只有一个属性，即链表的  。 Head 之后，我们只需在主函数中初始化列表并为其头赋予一个随机值为 10 的节点。 理解链表背后的关键是，现在   该属性 包含下一个节点。然后，最后一个节点将具有其 属性来跳转到下一个节点，依此类推。 Head 节点（由于其类型为 Node ）本质上将具有 Next 属性， Head Next 一旦我们向列表中添加一些节点，一切都会变得更加清晰，所以让我们开始吧！我们有两个选择：要么手动完成，这是一项 乏味的工作，要么为链表类编写一个方法来添加更多节点。让我们来看看！ 非常 添加节点：变相的可变列表 即使您几乎没有编程经验，在几乎每种编程语言中，您应该听说的第一个概念就是 和 列表之间的区别。 可变列表 不可变 顾名思义， 。相反，不可变元素具有 新元素。但为什么会这样呢？ 可变列表是您可以操作并向其添加元素的列表 固定的大小，并且不能添加 不可变列表 ，这意味着它们的元素 ：对于 3 个元素的列表，如果第一个元素存储在 0x00，那么第二个元素将存储在 0x01，最后一个元素将存储在 0x02。 在内存中是连续的 按顺序存储在内存中 这就是为什么在 Python 中迭代固定数组、不可变列表或元组是如此之快，因为 CPU 只是一一回忆内存索引。 另一方面，可变列表仅在首次初始化时在内存中是连续的：此时，如果添加元素，它们将不再是连续的。那么我们如何循环它们呢？ ，这将为我们带来附加的 to 元素，依此类推。 嗯，因为第一个启动的最后一个元素将有一个指针，该元素在其后面添加 所以，是的，可变列表实际上通常是变相的链接列表！ 现在，让我们看一下代码：   https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true 我们将方法 添加到链表的方法中。添加节点的过程如下： AddNode 首先，我们将 值存储在名为 的变量中 Head current 接下来，我们循环链表，每次用下一个节点更新 变量，直到下一个节点为空。 current 一旦我们当前所在的节点有一个空指针，我们就知道我们位于链表的最后一个节点。 最后，我们用一个新节点和一个新值更新最后一个节点（如果我们将其留空，则该新节点的 指针将设置为 null） Next 从图形上看，这个过程是这样的：  我们可以在主函数中检查该方法的正确功能，打印出链表中节点的值。 删除节点 现在是我们问题的最后一部分和解决方案：删除具有正确索引的节点。首先，从链表中删除节点是什么意思？如果我们想一想， ，对吧？ 链表中的节点只有与前一个节点相连才存在 例如，如果我们给 n-1ᵗʰ 的 值为 null，我们可以将 nᵗʰ 值从列表中断开。  Next 如果我们要删除的元素不是最后一个怎么办？好吧，我们可以 ！  通过将前一个元素连接到下一个元素来取消链接该元素 因此，要删除 kᵗʰ 元素，我们必须找到 k-1ᵗʰ 元素并将其链接到 k+1ᵗʰ 节点。我们需要存储  。 前一个节点 (k-1ᵗʰ) 显然， ：尝试像 这样的东西只会引发错误。不过，考虑到这一点，我们可以将列表的头视为索引 0，将其下一个节点视为索引 1，依此类推，并且我们也可以像之前所做的那样循环遍历节点。 我们不能直接索引列表 linkedlist[n] 然后我们可以做的是实现一个 来跟踪我们所在的节点！ 计数器 那我们就来编码一下吧。   https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true 让我们看一下接受 属性的 函数。之后，我们初始化三个变量： index RemoveNode    ，它将保存前一个节点 previousNode  ，它将保存我们在循环期间所在的节点 current  ，最初等于 0，这将保持我们在列表中的位置 counter 让我们暂时跳过第一个 if 块，专注于 for 循环。我们开始循环，直到 变量严格小于  ：然后每个循环将 counter index 用当前节点更新前一个节点，然后继续更新当前节点和计数器。 这意味着 指针，即   当循环中断时， 我们正好位于所需索引之前的节点上： 我们只需使用 我们所在的列表中的下一个节点来更新前一个节点 prev.Next 将是 current.Next 。最后，我们返回链表的头。 现在，如果要删除的索引是索引为 0 的头，会发生什么情况？循环永远不会启动，因为它将以 和 开始，并且条件将立即为 false。我们可以使用顶部的 if 块来管理第一种情况。 counter = 0 index = 0 基本上，如果索引为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 函数中，我们添加对该方法的调用，例如调用 和  ，我们可以检查结果中缺少节点 0 和节点 2 的情况。 ll.RemoveNode(0) ll.RemoveNode(2) 结论 我们已经走到了最后！ 如果你读到这里，我的全部感激之情都归于你。如果您愿意留下一两个赞并分享这篇文章，这会让我很高兴并帮助我继续写这些文章！ 下一篇文章见，一如既往，感谢您的阅读。 尼古拉

Read My Stories

該音頻是用故事的原始語言製作的！

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

About Author

註釋

標籤

这篇文章刊登在

Related Stories

点击赚钱：Telegram 可能会在 Solana 之前吸引下一个 100 亿加密用户

比特币 UTXO 模型，为独特的生态系统提供动力

想赢得 HackerNoon 写作比赛吗？以下是 #crypto-api 比赛获奖者的推荐

数字游民请注意：您需要了解泰国新推出的 DTV 签证

点击赚钱：Telegram 可能会在 Solana 之前吸引下一个 100 亿加密用户

比特币 UTXO 模型，为独特的生态系统提供动力

想赢得 HackerNoon 写作比赛吗？以下是 #crypto-api 比赛获奖者的推荐

数字游民请注意：您需要了解泰国新推出的 DTV 签证

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps