提问人：Eric Chen 提问时间：9/28/2023 最后编辑：Eric Chen 更新时间：9/28/2023 访问量：59
不同情况下单向链表的时间复杂度
Time complexity of singly linked list in different situations
问：
单链表有n个节点，提供了第i个节点的地址，分析以下情况。
1.假设第i个节点的地址不能更改，则在第i个节点和第i个节点之间添加一个新节点。
- 重复 1，但允许更改第 i 个节点的地址。
我认为无论它是否允许第 i 个节点的地址更改，时间复杂度都是 O（n），n 取决于链表的数量。
我不知道对第 i 个节点的地址是否发生变化的影响。
答：
1赞
Sergej Christoforov
9/28/2023
#1
你有一个对第i个节点的引用，你可以“更改地址”，然后你可以在ith之后插入一个新节点，并将第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） 操作。
评论