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.