微软面试题：如何O(1)删除单链表节点

来自：承香墨影作者：承香墨影 今天来做一道面试题：

在开始这个问题之前，先想想，如果给定单链表中的某个结点，如何在单链表中删除该节点？

对于一个单链表，它每个结点的数据结构除了存储自身的数据之外，还需要记录链表上，下一个结点的地址，通常我们将这个地址称之为后续指针 next。

那如上图所示，我想删除其中的 C 结点，需要做什么操作？很简单，将 B 结点的后续指针 next 指向 D 结点即可。

此处应该清晰了，要删除链表上的某个结点，我们需要知道三个结点：

• 待删除的结点。
• 待删除结点的前驱结点。
• 待删除结点的后续结点。

思路：实际删除下一个结点

再来回顾最开始的问题，当我们已知某个结点的时候，它的后续结点我们也是知道的。唯一的问题，就是他的前驱结点我们不知道。

最简单的解决方法，就是将链表遍历一遍，获得待删除结点的前驱结点，对其进行操作。

当涉及到遍历链表的时候，时间复杂度妥妥的变成 O(n)，这就与题不符了。

而问题主要卡在了，我们如何知道待删除结点的前驱结点。试着换一个思路想想，我们只需要删除该结点存储的数据，而并不是删除该结点对应地址中的内容。

那么就可以将待删除结点的 数据 ，和它的后续结点的 数据 进行互换，然后对它的后续结点进行删除操作，以此来达到 O(1) 时间复杂度的单链表删除。

涛声依旧注：也就是说不真正删除当前节点，只是把当前节点的数据放入到下个节点，删除下个节点，这样就等于删除了给定的节点。

问题：待删除节点是最后一个节点

这个思路还存在一个问题，我们实际删除的是待删除节点的下一个节点。还记得前面说，删除单链表中的某个结点，实际上是需要知道三个结点的。

那么，如果删除的结点，是单链表的最后一个结点，怎么办？

这时我们仍然需要从链表的头结点开始遍历，得到待删除节点的前驱节点，并完成删除操作，时间复杂度恢复到 O(n)。

而题目要求我们需要在 O(1) 的时间复杂度内完成删除操作，这样是不是不符合题目要求呢？

其实不然，假设单链表总共有 n 个节点，这种算法在 n-1 的情况下时间复杂度都是 O(1)，只有在待删除结点为单链表的最后一个结点时，时间复杂度才会恢复到 O(n)，那么平均时间复杂度：

[(n-1)*O(1)+O(n)]/n，计算下来仍然为 O(1)。

本文对你有帮助吗？留言、点赞、转发是最大的支持，谢谢！