Lintcode372 Delete Node in the Middle of Singly Linked List solution 题解
发布在刷题能手——Lintcode 题解2018年3月10日view:343
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.

给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。

【题目链接】

www.lintcode.com/en/problem/delete-node-in-the-middle-of-singly-linked-list/

【题目解析】

一般单链表删除某个节点,需要知道删除节点的前一个节点,则需要O(n)的遍历时间,显然常规思路是不行的。

在仔细看题目,换一种思路,既然不能在O(1)得到删除节点的前一个元素,但我们可以轻松得到后一个元素,这样,我们何不把后一个元素赋值给待删除节点,这样也就相当于是删除了当前元素。可见,该方法可行。

但如果待删除节点为最后一个节点,则不能按照以上思路。没有办法,只能按照常规方法遍历,时间复杂度为O(n),是不是不符合题目要求呢?可能很多人在这就会怀疑自己的思考,从而放弃这种思路,最后可能放弃这道题,这就是这道面试题有意思的地方,虽看简单,但是考察了大家的分析判断能力,是否拥有强大的心理,充分自信。

其实我们分析一下,仍然是满足题目要求的,如果删除节点为前面的n-1个节点,则时间复杂度为O(1),只有删除节点为最后一个时,时间复杂度才为O(n),所以平均的时间复杂度为:(O(1) * (n-1) + O(n))/n = O(1);仍然为O(1).

【参考答案】

www.jiuzhang.com/solutions/delete-node-in-the-middle-of-singly-linked-list/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏