It is certainly not possible with a plain singly-linked list.

Sketch proof: to examine the last node of a singly-linked list, we must perform `n-1`

operations of following a “next” pointer [proof by induction on the fact that there is only one reference to the `k+1`

th node, and it is in the `k`

th node, and it takes a operation to follow it]. For certain inputs, it is necessary to examine the last node (specifically, if the searched-for element is equal to or greater than its value). Hence for certain inputs, time required is proportional to `n`

.

You either need more time, or a different data structure.

Note that you can do it in O(log n) *comparisons* with a binary search. It’ll just take more *time* than that, so this fact is only of interest if comparisons are very much more expensive than list traversal.