首页 > 试题广场 >

在具有 n 个结点的单链表中，实现（ ）操作，其算法的

[单选题]
在具有 n 个结点的单链表中，实现（    ）操作，其算法的时间复杂度是 O（n）。 
  • 遍历链表或求链表的第 i 个结点
  • 在地址为 P 的结点之后插入一个结点
  • 删除开始结点
  • 删除地址为 P 的结点的后继结点
查看正确选项
添加回答
小怪兽：不疼(๑•.•๑)头像 小怪兽：不疼(๑•.•๑)
选a 遍历的时间复杂度为O（n），i不知道指定的前驱节点 所以也为 O（n）
发表于 2017-11-03 19:16:35 回复(0)
诚心诚意求一个offer的菜鸡头像 诚心诚意求一个offer的菜鸡
A：很明显是对的
B，D：很容易理解错误，B，D答案的意思是只是针对插入和删除这个动作的时间复杂度是多少，应该为O(1)
C：时间复杂度为O(1)
发表于 2018-11-27 17:14:53 回复(0)
论超几何分布头像 论超几何分布
插入和删除属于简单操作o（1） 遍历则更复杂
编辑于 2020-10-16 08:12:53 回复(0)
干炸带鱼头像 干炸带鱼
只有查询的时间复杂度是ON,其他插删改都是一次操作
发表于 2021-09-29 13:05:59 回复(0)
凡尘的光头像 凡尘的光
A
编辑于 2024-04-11 17:30:04 回复(0)
已注销头像 已注销
A.强调遍历，链表遍历是O(n)
BCD强调插入删除，在知道插入删除的位置后时间复杂度为O(1)
发表于 2022-12-14 10:06:31 回复(0)
牛客965840016号头像 牛客965840016号
a
发表于 2021-09-27 21:42:29 回复(0)
白开水和咖啡头像 白开水和咖啡
B,D选项，结点的地址p已经给定，对其后继节点的操作，复杂度为O（1）
发表于 2019-08-26 07:06:36 回复(0)
侯卿头像 侯卿
啥叫"都是"，i为1就不是。。。。不过bcd都是O(1)。。
发表于 2018-01-18 19:17:17 回复(0)
klgo头像 klgo
链表是顺序存储时间复杂度为O(N)
发表于 2017-10-31 21:13:07 回复(1)
提交观点

问题信息

链表
上传者：阿奻_
难度：
10条回答 15958浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号