Assuming it's a linked list seems like a bit of a cheat to do it in linear time. Pairing off mismatched elements to preserve the invariant is the right approach, but we only need to keep track of one "candidate value", and how many times we've seen it.

So, initialize the count to zero. Now, consider each array element in turn. If your count is zero, set it to one and set the candidate value to that of the current element. Otherwise, compare the current element's value to the candidate value. If they match, increment the count, and if they don't, decrement it. You'll be left with a non-zero count and the candidate value will be the one that appeared more than n/2 times.