首页 > 试题广场 >

在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持

[单选题]
在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 。 
  • O（1）
  • O（n）
  • O（n2）
  • O（nlog2n）
查看答案及解析
添加回答
jranzjm头像 jranzjm
单链表插入时间应该是O（1），但要维持有序状态，就应该从头结点开始逐个进行比较扫描，最好情况O（1），最坏O（N），平均情况~N/2
个人浅见，不知道是否正确。
发表于 2017-12-07 23:38:42 回复(4)
karaysn头像 karaysn
我觉得是应该先要查找，这里花的时间比较多，o(n),然后插入这个是0(1),总的就是o(n)吧
发表于 2017-10-28 10:29:02 回复(0)
XXXX.RYJ头像 XXXX.RYJ
插入的这个过程时间复杂度虽然是O（1），但是遍历的这个过程时间复杂度为O（n）。
发表于 2020-06-13 00:19:53 回复(0)
牛客284614939号头像 牛客284614939号
最好的情况：
从头结点扫描到末尾，时间复杂度O(n)
发现只需要插入到最末尾，也就是O(1）

因此，时间复杂度是O(n)
发表于 2022-11-04 15:28:44 回复(0)
比伯燃头像 比伯燃
有序指在单链表中指定位置插入指定元素的时间复杂度，长度为n单链表中找到指定位置时间复杂度为O(n),插入元素时间复杂度O(1)
发表于 2022-09-19 08:50:08 回复(0)
HI_YONGGE头像 HI_YONGGE
有序指在单链表中指定位置插入指定元素的时间复杂度，长度为n单链表中找到指定位置时间复杂度为O(n),插入元素时间复杂度O(1)
发表于 2020-05-21 21:49:46 回复(0)
云霜连绛阙头像 云霜连绛阙
先遍历后插入。遍历O(n)，插入O(1)，加起来O(n)
发表于 2019-03-13 09:22:30 回复(0)
侯卿头像 侯卿
插入忽略，单链表的查找只能从头开始往后找，复杂度为O(N)。
发表于 2018-01-15 20:50:44 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 链表 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 远景 测试开发工程师 大数据开发工程师 Java工程师
上传者：蜡蜡
难度：
8条回答 13394浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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