题19

题19

题目

在长度为 的有序单链表中插入一个新结点,并仍然保持有序的时间复杂度是 ( ).
A.
B.
C.
D.

分析

这种就是插入排序的复杂度吧，插入排序的复杂度是D
原来题目说了是单链表，这就表明，题目所给的链表已经是有序的了

解

B
设单链表递增有序,首先要在单链表中找到第一个大于 的结点的直接前驱 ,在 之后插入该结点。
查找的时间复杂度为 ，插入的时间复杂度为 ，总时间复杂度为 。