数据结构题目;在一个具有n个结点的有序单链表中手插入一个新结点并依保持为有序单链表的时间复杂度为

1)首先，为使得插入后的序列仍然有序，需要把插入的结点和原来的结点一一比较，直到找到一个比插入结点大的（我们假设原来的序列按递增排列），这时就可以插入到比它大的结点的前面；
2)其次，设原序列有n个结点，则有新结点有n+1个空位可以插入，插入到第一个空位需要比较1次，第二个空位比较2次。。。。第n个空位比较n次，第n+1个空位不需要比较
3)最后，假设每个空位插入的可能性相同，因此，时间复杂度为1/(n+1) * (1+2+...+n)=1/(n+1) * (n+1)n/2=n/2，记为O(n)

最多N次 最少1次
（N+1）/2