The negation of this sentence can be kind of nuanced, especially for a nonnative English speaker (which I assume you are because of the misplaced verb in the question). I'm assuming you want the negation of the sentence,
> All redheaded persons in the room have a pet that is either a cat or a dog.
This is kind of tricky because there is an implied 'and' in the sentence. With the 'and' included, it should be,
> All redheaded persons in the room have a pet **AND** that pet is either a cat or a dog.
So the negation of this sentence would be,
There exists a redheaded person in the room who has no pet or has a pet which is not a cat or dog.