Non-deterministic algorithm to check if a list has some given value
If the only way you have to access the last element is to step through the whole list, one item at a time, you can't possibly use less than $O(n)$ time, even nondeterministically. If you used less than that, none of the paths through the computation would be able to access the end of the list, so none of them would be able to check whether it contained the desired entry.