Question

单链表中有n个结点，这其中查找值为x的结点，在查找成功时需要比较的平均次数是多少？还有如果查找失败？

内容能否详细点

Answer 1

如果查找的是第一个是比较1次，第二个是2次第n个是n次，要查找的元素每个概率相等即每个为1/n
所以平均是(1/n)(1+2+3+……n)=(1+n)/2次
查找失败是即是每个都查找了一遍都没找到所以是n次.
只能这样解释了，如果有疑问可以再问。