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+1th node, and it is in the
kth 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
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.