问题：实现一个函数，指定链表在平均时间复杂度为O(1)删除该链表的指定结点

该链表时单链表。

原理：

常规的删除方法是从链表头开始遍历链表，如果找到结点就修改该结点的前驱指针指向该结点的后继。如果该结点是最后一个结点就把前驱指向NULL。但这个问题有时间复杂度要求O(1)，不能使用这种方法。

根据题目的条件，我们可以知道指定要删除的结点和它的后继，如果后继非空，把后继的值覆盖到要删除的结点，同时把要删除的结点的后继指向后继的后继。这样，给定的结点并没有删除，但它的值被后继的值覆盖，这就相当于间接删除了给定结点。

有两点点要注意。（1）如果给定的结点为链表的最后一个结点，就无法使用上面的思路。需要从头遍历链表。这时平均时间复杂度还是O(((n-1)*1+n)/n)=O(1)满足要求。（2）如果给点结点就是头结点且链表只有一个结点就直接把head设置为NULL。

实现：

定义结点

1
2
3
4
5
6
7
8
class Node:

    def __init__(self, value):
        self.value = value
        self.next = None

    def __repr__(self):
        return "Node<{}>".format(self.value)

实现删除链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def delete_node(p_head, node):
    if not p_head or not node:
        return False
    # 使用覆盖思路
    if node.next:
        node.value = node.next.value
        node.next = node.next.next
    # 删除只有一个结点的链表
    elif p_head == node and p_head.next is None:
        p_head = None
        node = None
        return True
    # 删除最后的结点
    else:
        p_node = p_head
        while p_node.next != node:
            p_node = p_node.next
        p_node.next = None
        return True
    # 给定的结点不属于链表
    return False

简单的测试代码，这里不列出极端测试样例，可自行测试。

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
def build_linked_list(values):
    if not values:
        return None
    root = Node(values[0])
    p_node = root
    for value in values[1:]:
        p_node.next = Node(value)
        p_node = p_node.next
    return root

def main():
    p_head = build_linked_list([1, 2, 3, 4, 5])
    node_3 = p_head.next.next # Node<3>
    delete_node(p_head, node_3)
    for node in travel_list(p_head):
        print(node, end='\t')

    print('\n')
    print('delete last node')
    node_5 = p_head.next.next.next
    delete_node(p_head, node_5)
    for node in travel_list(p_head):
        print(node, end='\t')

if __name__ == '__main__':
    main()

输出结果

1
2
3
4
Node<1> Node<2> Node<4> Node<5>

delete last node
Node<1> Node<2> Node<4>

完。