在O(1)的时间内删除结点

本文主要是介绍在O(1)的时间内删除结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

剑指Offer_13: 在$O(1)$的时间内删除结点

---

2018/05/14 星期一

题目: 给定单项链表的头指针和一个结点指针，定义一个函数在$O(1)​$的时间删除该结点。链表结点和函数的定义如下：

class ListNode {int data;ListNode nextNode;
}
public void deleteNode(ListNode head, ListNode deListNode)

思考三分钟。。。。

在单链表中删除一个结点，最简单的方法无疑就是从链表的头结点开始，顺序遍历查找要删除的结点，并在链表中删除该结点。

• 上图(a)中表示一个单链表
• 上图(b)中，表示顺序遍历删除i结点。删除i结点之前，先从头结点开始遍历到i前面的一个结点h，然后把h结点的指针指向i的下一个节点j，再删除节点i(常规思路复杂度$O(n)$)。
• 上图(c)中，把结点j中的内容复制到结点i中，再把i中的指针指向节点j的指针。这种方法不用遍历i结点前面的元素。时间复杂度为$O(1)$

基于图(c)的思路中还需要考虑一个问题，如果更新的节点位于链表的尾部(尾结点)，怎么办，它没有下一个节点？这时候只能通过顺序遍历查找（图（b）中表示的方法）。如果我们有一个节点，删除的位置即是头结点也是尾结点，当我们在删除的时候除了删除节点还是将头结点置为null。完整代码如下：

public void deleteNode(ListNode head, ListNode deListNode) {if (deListNode == null || head == null) {return;}// 如果删除头结点if (head == deListNode) {head = null;} else {// 如果删除结点为尾结点if (deListNode.nextNode == null) {ListNode pointListNode = head;while (pointListNode.nextNode.nextNode != null) {pointListNode = pointListNode.nextNode;}pointListNode.nextNode = null;} else {deListNode.data = deListNode.nextNode.data;deListNode.nextNode = deListNode.nextNode.nextNode;}}
}

算法的时间复杂度：对于n-1个非尾结点而言，我们是可以在$O(1)$的时间内完成操作；对于尾结点我们仍然需要顺序查找，时间复杂度为$O(n)$。总的平均时间复杂度是$\frac {[(n-1)*O(1)+O(n)]}n$，结果还是$O(1)$。

上述的代码并不是完美的代码，它基于一个假设，那就是要删除的结点存在链表当中。

测试用例：

1. 功能测试：删除多个结点链表的中间结点，头结点，尾结点等；从只有一个结点的链表中删除唯一结点。
2. 特殊输入测试：

这篇关于在O(1)的时间内删除结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---