paint-brush
日常编码问题:一次性从链表中删除第 k 个索引经过@nicolam94
618 讀數
618 讀數

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

经过 Nicola Moro8m2023/06/26
Read on Terminal Reader

太長; 讀書

我们得到一个链表和一个要从列表中删除的索引元素“k”。之后,我们应该返回链表的头。我们必须一次性完成所有这些操作,这意味着我们不能多次循环列表。让我们看看如何!
featured image - 日常编码问题:一次性从链表中删除第 k 个索引
Nicola Moro HackerNoon profile picture

一次性从链表中删除第 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 = 0index = 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 的情况。


结论

我们已经走到了最后!


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


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


尼古拉