快速删除链表节点

# 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;
}