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

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

---

2018/05/14 星期一

题目: 给定单项链表的头指针和一个结点指针，定义一个函数在O(1)​$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)$O(n)$)。
• 上图(c)中，把结点j中的内容复制到结点i中，再把i中的指针指向节点j的指针。这种方法不用遍历i结点前面的元素。时间复杂度为O(1)$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(1)$的时间内完成操作；对于尾结点我们仍然需要顺序查找，时间复杂度为O(n)$O(n)$。总的平均时间复杂度是[(n−1)∗O(1)+O(n)]n$\frac{[(n-1)\ast O(1)+O(n)]}{n}$，结果还是O(1)$O(1)$。

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

测试用例：

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