快速删除链表节点

1. 题目描述

给定单向链表的头指针和一个结点指针，定义一个函数在 $O(1)$ 时间删除该结点。

2. 思路描述

正常的做法肯定是在 $O(N)$ 时间内删除节点。而这么过分的要求，显然是通过“重新赋值”才能做到。

比如要删除节点 a，那么就将 a.next 的 value 和 next 赋值给节点 a，然后删除 a.next。

表面“看起来”像是删除了节点 a，其实是将其后节点的信息转移到了它自己身上。

除此之外，对于最后一个节点，还是要退化成 $O(N)$ 的复杂度。而整体分析一下复杂度：

$$
O(T) = (O(N) + O(1) * (n - 1)) / n = O(1)
$$

3. 代码实现

class Node {
    /**
     * 节点构造函数
     * @param {*} value
     * @param {Node} next
     */
    constructor(value, next) {
        this.value = value
        this.next = next
    }
}

/**
 *
 * @param {Node} head
 * @param {Node} toDelete
 */
function deleteNode(head, toDelete) {
    if (head === toDelete || !toDelete || !head) {
        return
    }

    let nextNode = toDelete.next

    if (!nextNode) {
        // 尾节点
        let node = head
        while (node.next !== toDelete) {
            node = node.next
        }
        node.next = null
        toDelete = null
    } else {
        toDelete.value = nextNode.value
        toDelete.next = nextNode.next
        nextNode = null
    }
}

/**
 * 测试代码
 */

let node3 = new Node(3, null),
    node2 = new Node(2, node3),
    node1 = new Node(1, node2),
    head = new Node(null, node1)

deleteNode(head, node2)
let node = head.next
while (node) {
    console.log(node.value)
    node = node.next
}