在单链表中,若要在第i个位置插入一个新节点,已知第i-1个节点的指针,以下关于插入操作的时间复杂度描述正确的是?
答案解析
在单链表中,如果已知第i-1个节点的指针,插入新节点的时间复杂度为O(1),因为只需要修改第i-1个节点的指针指向新节点,新节点的指针指向原来的第i个节点即可。选项B、C、D描述的时间复杂度均不正确,因为B忽略了已知前驱节点的情况,C和D与链表插入操作的时间复杂度无关。
正确答案:A