[beder]

You can do a second pass over the list to check that your solution is actually a majority element. This maintains the linear time and constant space properties.

[justincormack]

Unfortunately single pass is usually the binding constraint eg real time data processing.