O(1)时间内删除单链表节点

这是唯品会实习生招聘的压轴题 首先吐槽下vip.com ,暑期实习生一共才招21人!太少了吧!

笔试现场各种乱,Java,Android,Tester,PHP,IOS甚至还有管培,产品经理这些,全坐一起,…人挨人的

笔试题更坑爹啊!前面选择题,都是Java语法题,感觉没多大含金量。

大题更坑啊!操作系统,网络,组成原理,算法各一题 其中前三者,都是考死知识,神马解释操作系统进程通信方式,解释段页式管理,解释TCP和UDP

最后的算法题还算不错!

题目是:O(1)时间内删除单链表节点 拿到这道题的第一想法是,我擦!你TMD逗我呢!这TMD也可能实现?!

寻思一番之后,突然发现,卧槽!这真的可以实现啊!

好吧,开始进入正题。

在单链表中删除一个节点,最常规的做法无疑是从链表的头结点开始顺序遍历,查找要删除的节点,并删除节点。 这种思路因为要顺序查找,时间复杂度当然是O(n)了

我们之所以要从头开始查找,是因为我们要得到被删除节点的前一个节点。在单链表中,没有指向前一个节点的指针,于是只能遍历咯!

一定要遍历吗?当然不一定啦!不然这篇博文在写神马?

重点来啦!!

我们可以很方便的得到待删除节点的下一个节点。如果我们把下一个节点的内容复制到待删除的节点上,再把下一个节点删除掉,那是不是相当于删除了当前需要删除的节点? 好了,大致思路就是这样的。知道思路了,代码也很容易写出来了。这里就省去咯!

还有一个问题。万一要删除的节点是尾节点呢?尾节点没有下一个节点哟! 没办法,只能顺序遍历咯!

最后需要注意的是,如果链表只有一个节点的情况。 这种情况只要把链表置Null就OK啦!