不同情况下单链表的时间复杂度

Question

单链表有n个节点，给出第i个节点的地址，分析以下情况。

1.在第(i-1)个节点和第i个节点之间添加一个新节点，假设第i个节点的地址不能改变。

2. 重复1，但允许第i个节点的地址改变。

我认为无论是否允许第i个节点的地址改变，时间复杂度都是O(n)，n取决于链表的数量。

不知道第i个节点的地址是否变化有什么影响

Answer 1

你有一个对第i个节点的引用，你可以“更改地址”，然后你可以在第i个节点之后插入一个新节点，并将第i个节点的内容复制到新节点：

// `node` is a reference to the i-th node
// `value` is a value for a new inserted node
struct node *new_node = malloc(sizeof(struct node));
new_node->next = node->next;
new_node->value = node->value; // copy the content
node->next = new_node;
node->value = value;

这是一个 O(1) 操作。