单链表查找值为x的节点从一个具有n个节点的单链表中查找其值等于x的节点，在查找成功的情况下，平均需要比较几个结点，说下原因？

2021-03-16

1487

从一个具有n个节点的单链表中查找其值等于x的节点，在查找成功的情况下，平均需要比较几个结点，说下原因？要从包含n个节点的单链表中找到值等于x的节点，我们需要在搜索成功时平均比较（n1）/2个节点。由于

从一个具有n个节点的单链表中查找其值等于x的节点，在查找成功的情况下，平均需要比较几个结点，说下原因？

要从包含n个节点的单链表中找到值等于x的节点，我们需要在搜索成功时平均比较（n1）/2个节点。

由于单链表只能执行单向顺序搜索，因此以从第一个节点开始的搜索为例，需要比较的节点数f（m）=m才能找到第m个节点。搜索成功的最佳情况是第一次搜索成功，只比较一个节点，最坏情况是最后一次搜索成功，需要比较n个节点。

总共有n个案例，要比较的平均节点是（1，2，3。。。（n-1）n）/n=（n 1）/2。