如何删除一个链表节点?

如何删除一个链表节点?

面试时的老问题了,考考对链表的理解,似乎没有什么好说的。很多同学一听这个问题,马上就能反应过来:从头开始遍历删除,时间复杂度O(n),下一题,请。

这样回答证明你还是懂一点链表知识的,差不多就行了。但是,我个人觉得这是一个开放性题目。如果我是面试官,我希望回答者能想到各种情景,或者询问追加条件,给他更多展示的机会。

“如何删除一个链表节点?”其实也算是一个需求,有需求就必须先理解再动手,不仅应该搞清楚“我”想怎么删,最好能给出几个删除的解决方案让“我”选择,并且详解利弊,这才能拿到满分。

一、什么链表

首先搞清楚是个怎样的链表,如果没有明确指定,那么基本上可分为单链表和双链表。

(1)单链表

知道链表形式后,需要搞清楚要删的节点是个什么情况。

1.告诉你头结点 + 要删除的节点的值

这个实在是木有办法,只能从头开始遍历,最坏情况是遍历最后一个节点才找到,时间复杂度O(n)。

删除节点的要点其实是如何把链表接上,所以要随时记录要删节点的上一个节点的指针。

2.告诉你头结点 + 要删除的节点的指针

假设现在存在 A->B->C->D->E 五个顺序节点,我们只知道C的位置,如果要删除C,那么就得链接 B->D ,该怎么做呢?

1、解法1

虽然知道了要删的节点C在哪里,但是因为是单链表,无法知道上一个节点B的位置,所以在删除节点后无法把链表接上。

想要知道上一个节点B的位置,还是只能从头A开始遍历,通过对比内存位置找到当前C节点,拿到下一个节点D节点,并且拿到上一个B节点,实现对接。

一套操作下来,时间复杂度还是O(n)。

如果你是这样想的,那么就中招了。

2、解法2

这种情况一般以此种面试题出现:

给定链表的头指针和一个结点指针,在O(1)时间删除该结点。

我们不妨换一种思路。

既然知道了C节点,那么C指向的必然是D。与其搞清楚B节点在哪里,我们不如把C节点直接变成D节点,不就完成 B->D 的对接了吗?

实际上,就是把D的值赋给C,然后把D指向E的指针覆盖C指向D的指针。虽然B节点的指针依然指向C节点的位置,但是C节点的内容已经完全变成D节点的内容了,也就完成了对接(虽然C节点的位置还在,但是内容消失了,其实就是删除)。时间复杂度O(1).

只想到这一步是不是又搞定了?不好意思你又中招了…

3、补充

2中容易漏掉一种情况:如果要删除的是E节点,那么E节点木有下一个节点了…现在我们要做的就是干掉D节点指向E节点的指针。

如何找到D节点呢?只有从A节点开始遍历了…这就是为什么这道题目要给出一个头结点,就是这种情况下要用到的。这种情况下时间复杂度又是O(n)。

题目要求我们需要在O(1)时间完成删除操作,那岂不是完蛋了?

实际上,假设链表总共有n个结点,这种算法在n-1种情况下时间复杂度是O(1),只有当给定的结点处于链表末尾的时候,时间复杂度为O(n)。

平均时间复杂度要这样计算:[(n-1)*O(1)+O(n)]/n,时间复杂度仍然为O(1)。

(2)双链表

1.告诉你要删除的节点指针

既然是双链表,那么前后节点的位置你都知道了…时间复杂度O(1),不用多说。

2.告诉你头节点 + 尾节点 + 要删除的节点的值

如果只告诉你头结点在哪里,那么只能从头开始遍历。如果告诉你头尾节点在哪里,那么可以同时从头尾开始遍历,减少找到目标节点的花费。

举个例子:一个逃犯藏在一列火车的某一节车厢中。如果一个警察从车头找到车尾,最坏情况要n节车厢才能找到,时间复杂度是O(n)。但是如果两个警察从车头车尾包夹,最坏情况在n节车厢正中就能找到,时间复杂度是O(n/2),效率高了一半。

二、总结

很简单的问题,稍微娱乐一下。

发布者

xie4ever

发表评论

电子邮件地址不会被公开。