一次性从链表中删除第 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) 结论 我们已经走到了最后! 如果你读到这里,我的全部感激之情都归于你。如果您愿意留下一两个赞并分享这篇文章,这会让我很高兴并帮助我继续写这些文章! 下一篇文章见,一如既往,感谢您的阅读。 尼古拉