首页 > 试题广场 >

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

[单选题]
在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。 
  • O(1)
  • O(n)
  • O(n2)
  • O(log2n)
查看答案及解析
添加回答
大星星和小猩猩头像 大星星和小猩猩
有时候真的不知道这些题目想考的是“ 插入 ”这个操作自身，还是别的什么鬼
发表于 2018-05-06 16:40:48 回复(0)
BugFree头像 BugFree
需要遍历O（n）。确定位置再插入，插入的时间复杂度是O（1）
发表于 2017-08-03 17:10:46 回复(1)
Andrew9646头像 Andrew9646
有序并且为了保持顺序，那么插入时首先要依次向后挪移一个元素，然后再插入
发表于 2021-08-16 12:13:55 回复(1)
锄锄chu头像 锄锄chu
要遍历一次链表，找到要插入位置的前一个节点
发表于 2022-07-27 13:00:27 回复(0)
牛客109541727号头像 牛客109541727号
这个插入真的不明不白的，如果我有链表有头结点和尾结点，那么插入（到最后一个元素）就是O（1），如果没有尾结点，那最坏的插入情况就是O（n）
发表于 2022-04-19 22:52:00 回复(0)
手心的蔷薇201903212357198头像 手心的蔷薇201903212357198
遍历是o(n)，插入是o(1)
发表于 2020-11-12 11:57:36 回复(0)
人要学会珍惜头像 人要学会珍惜
遍历，遍历，遍历！！！
发表于 2023-08-20 15:46:04 回复(0)
子若无鱼头像 子若无鱼
遍历链表，查找到要插入位置的前一个节点

发表于 2022-11-30 18:17:14 回复(0)
Ryzain头像 Ryzain
<p>为啥不能用二分法</p>
发表于 2021-01-20 15:49:14 回复(1)
Fcq11头像 Fcq11
需要先找到插入位置
发表于 2020-03-21 10:34:56 回复(0)
hpjk07头像 hpjk07
需要先遍历，再查找到位置插入，所以是O(n)
发表于 2019-03-21 22:59:13 回复(0)
恨自己不够强头像 恨自己不够强
遍历的时间复杂度为O(n),
发表于 2019-03-13 09:26:28 回复(0)
我牛客最菜打钱头像 我牛客最菜打钱
玛德，有序
发表于 2018-09-16 23:37:24 回复(0)
拿着菜刀的白菜头像 拿着菜刀的白菜
我不想再吐槽这题了。。。
发表于 2018-05-17 14:06:35 回复(0)
提交观点

问题信息

链表
上传者：蜡蜡
难度：
14条回答 2408浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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