设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单_欢聚集团笔试题

推荐

牛客-007

答案：D

首先要找打插入位置，

由于单链表不能像顺序表那样二分查找，因此只能顺序查找，查找的时间复杂度为O（n）

其次是插入，链表的插入操作时间复杂度是O（1）

因此总的操作时间复杂度为O(n)

编辑于 2015-01-31 10:59:29 回复(0)

newcomer

必须要注意的是，单链表不能进行二分查找。原因在于，二分查找是基于下标操作的，也就是类似数组那种连续存储的顺序表才能使用；而单链表是通过指针来链接的。

要使得插入后还有序，则必须首先找到位置，即O(n)，然后修改链表，即O(1),所以总的时间复杂度为O(n)。

发表于 2015-07-05 09:04:53 回复(0)

Tonny不拖泥

复杂度就是基本语句重复的次数

发表于 2018-09-10 23:11:00 回复(0)

一瓢之饮

两方面：一是插入时间复杂度O(1)；二是保持有序时间复杂度O(n)

发表于 2017-08-31 09:33:17 回复(0)

柳逗逗

这个不是最坏的情况下的时间复杂度么？

发表于 2016-09-19 15:35:33 回复(1)

流亡者号

有序的单链表是一种线性数据结构，其特点是所有结点按照结点的值（如数值、字符等）以特定顺序（升序或降序）排列。

发表于 2025-03-20 12:27:53 回复(0)

BugFree

得先查找，定位到需要插入的位置，再插入，总的复杂度O(n)+O(1)

编辑于 2017-09-02 23:53:06 回复(4)

offer冲鸭

单链表不能进行二分查找，只能从头开始查

发表于 2019-02-24 10:47:21 回复(0)

诚心诚意求一个offer的菜鸡

链表查找要一个一个的查找，查找的时间复杂度为O(n)

插入的时间复杂度为O(1)

所以总的时间复杂度为O(n)

发表于 2018-12-09 21:14:03 回复(0)

小黑201807241511744

最坏时间复杂度是：O（n）
最好时间复杂度是：O（1）
可以求平均时间复杂度：
每一种情况出现的可能性相同所以概率都为1/n+1
1/n+1 + 2/n+1 + 3/n+3 ··········+ n/n+1
= (n+1)*n/ n+1 (等差数列求和)
=n

发表于 2018-09-30 16:45:33 回复(1)

lilinl

单链表只能顺序查找，不管有序还是无序

发表于 2018-07-22 21:35:27 回复(0)

vcjmhg

查找耗费了时间复杂度

发表于 2016-11-20 22:20:31 回复(0)

小雨落梧桐

D

发表于 2015-04-20 15:41:43 回复(0)

CS sky

D 二分查找的时间复杂度确实小但是二分查找仅仅用于有序的情况下

发表于 2015-01-19 12:57:31 回复(1)

设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单

问题信息

热门推荐

相关试题