10. 如何在O(1)时间复杂度内删除链表的节点？

在链表中删除节点通常需要遍历链表来找到要删除节点的前驱节点，然后更新其指针。对于单链表，这种操作的时间复杂度通常为 O(n)，其中 n 是链表的长度。然而，有一种特殊情况可以在 O(1) 时间复杂度内删除节点，即当你已知要删除的节点本身时，而不是从链表头开始进行查找。

1. 问题描述

假设你有一个单链表，并且你已经有了指向某个节点的指针（假设不是链表的尾节点）。你的任务是直接在 O(1) 时间复杂度内删除这个节点，而不需要遍历链表。

2. 删除节点的技巧

为了在 O(1) 时间复杂度内删除节点，可以采取以下方法：

• 复制下一个节点的值到当前节点：将当前节点的值替换为下一个节点的值。
• 删除下一个节点：然后删除下一个节点（将当前节点的 next 指针指向下下一个节点）。

通过这种方式，相当于将当前节点的内容替换为下一个节点的内容，并删除下一个节点，而在逻辑上达到删除当前节点的效果。

3. 示例代码

以下是一个 Java 示例，展示了如何在 O(1) 时间复杂度内删除链表的节点。

public class LinkedList {
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    public LinkedList() {
        this.head = null;
    }

    // 在链表末尾添加节点
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    // 打印链表中的所有节点
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 在 O(1) 时间复杂度内删除节点
    public void deleteNode(Node node) {
        if (node == null || node.next == null) {
            throw new IllegalArgumentException("Invalid node or tail node cannot be deleted using this method.");
        }

        // 将下一个节点的值复制到当前节点
        node.data = node.next.data;

        // 删除下一个节点
        node.next = node.next.next;
    }

    // 获取链表中的某个节点（便于测试）
    public Node getNode(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.append(4);
        list.append(5);

        System.out.println("Original List:");
        list.printList();

        Node nodeToDelete = list.getNode(3); // 假设我们要删除值为 3 的节点
        list.deleteNode(nodeToDelete);

        System.out.println("List after deleting node 3:");
        list.printList();
    }
}

输出示例：

Original List:
1 -> 2 -> 3 -> 4 -> 5 -> null
List after deleting node 3:
1 -> 2 -> 4 -> 5 -> null

4. 解释

• 复制值：node.data = node.next.data 将下一个节点的值复制到当前节点。
• 删除节点：node.next = node.next.next 将当前节点的 next 指针指向下下个节点，从而删除了原来的下一个节点。

5. 注意事项

• 尾节点：此方法不能用于删除尾节点（链表的最后一个节点），因为尾节点没有后继节点。如果尝试删除尾节点，复制操作会失败。
• 逻辑删除：此方法并未真正删除当前节点，而是将当前节点“替换”为下一个节点。对于使用内存管理的语言（如 C++），这可能导致内存泄漏，但在 Java 中，由于垃圾回收机制，这不构成问题。

6. 总结

在 O(1) 时间复杂度内删除链表中的节点是通过将当前节点的值替换为下一个节点的值，并删除下一个节点来实现的。这种方法适用于删除非尾节点的场景，极大地优化了删除操作的效率。