beder parent
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.
Unfortunately single pass is usually the binding constraint eg real time data processing.