在具有n个结点的单链表中,实现下列哪些操作,其算法的时间复杂度都是O（n)?a)遍历链表和求链表的第i个结点b)在地址为p的结点之后插入一个结点c)删除开始结点d)删除地址为p的结点的后继结

Question

在具有n 个结点的单链表中,实现下列哪些操作,其算法的时间复杂度都是O（n)?
a)遍历链表和求链表的第i个结点
b)在地址为p的结点之后插入一个结点
c)删除开始结点
d)删除地址为p的结点的后继结点

Answer 1

a）平均复杂度为（n+1)/2;
b) 平均复杂度为 （n+1)/2;
c) 平均复杂度为 1;
d) 平均复杂度为 （n+1)/2;
所以a)、b)、d)的时间复杂度均为O(n);
c）为O（1）；