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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54