😀前言
在链表操作中，删除节点是一个常见的操作。然而，如何在最短的时间内完成删除节点的操作是一个值得探讨的问题。通常情况下，删除链表节点需要遍历链表来找到目标节点及其前驱节点，时间复杂度为 O(N)。但是，通过巧妙的设计，可以在 O(1) 的时间内完成删除操作。本文将详细介绍这一算法及其实现。

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

😋解题思路

我们可以将删除节点的操作分为两种情况来处理：

🤔情况 1：删除的节点不是尾节点

如果要删除的节点不是链表的尾节点，那么我们可以通过以下步骤来实现删除：

1. 将下一个节点的值赋给当前节点：例如，我们要删除节点 A，可以将 A 的下一个节点 B 的值复制到 A。
2. 调整指针：令 A 指向 B 的下一个节点，从而跳过节点 B。
3. 删除节点 B：这样，节点 A 依然存在于链表中，但它的值和位置实际上已经是原节点 B 的值和位置，节点 B 被删除了。

这一过程无需遍历链表，时间复杂度为 O(1)。

🤔情况 2：删除的节点是尾节点

如果要删除的节点是链表的尾节点，处理就会稍微复杂一些：

1. 遍历链表：找到要删除节点的前一个节点。
2. 调整指针：将前一个节点的 next 指针置为 null，从而删除尾节点。

由于需要遍历整个链表来找到前驱节点，因此时间复杂度为 O(N)。

综上，如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)。

😃Java 实现

以下是上述思路的 Java 实现：

public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
    if (head == null || tobeDelete == null)
        return null;
    if (tobeDelete.next != null) {
        // 要删除的节点不是尾节点
        ListNode next = tobeDelete.next;
        tobeDelete.val = next.val;
        tobeDelete.next = next.next;
    } else {
        if (head == tobeDelete)
             // 只有一个节点
            head = null;
        else {
            ListNode cur = head;
            while (cur.next != tobeDelete)
                cur = cur.next;
            cur.next = null;
        }
    }
    return head;
}

🥰代码解析

1. 入口方法 deleteNode：
   • 处理特殊情况：首先检查输入的链表头节点和要删除的节点是否为 null，若是则直接返回 null。
   • 如果要删除的节点不是尾节点，直接将下一个节点的值复制到当前节点，调整当前节点的 next 指针，跳过下一个节点。
   • 如果要删除的节点是尾节点，则需要遍历链表找到前驱节点，并将前驱节点的 next 指针置为 null。
2. 处理尾节点：
   • 如果链表只有一个节点，直接将链表头设为 null。
   • 如果链表有多个节点，则遍历链表找到尾节点的前驱节点，并调整指针。

😊示例分析

假设链表为 1 -> 2 -> 3 -> 4 -> 5，我们要删除节点 3。根据上面的算法，节点 3 将被节点 4 的值覆盖，链表变为 1 -> 2 -> 4 -> 4 -> 5。随后，节点 4 的 next 指向节点 5，最终链表变为 1 -> 2 -> 4 -> 5，实现了删除节点 3 的效果。

😄总结

本文介绍了一种在 O(1) 时间内删除链表节点的算法，通过区分要删除的节点是否为尾节点来进行不同的处理。对于非尾节点，可以通过复制和指针调整在常数时间内完成删除操作；对于尾节点，则需要遍历链表找到前驱节点，时间复杂度为 O(N)。整体来看，该算法的平均时间复杂度为 O(1)，是处理链表删除问题的高效方法。