You always keep pairs of carriages, connected like this:

  +----------------+ +---------------+
  |               T| |               |
  +----------------+ +---------------+
    O            O     O            O

where 'T' marks a toilet. You build your train from a bunch of those cars, and now it does not matter how you connect them, you'll always have a toilet within a car's range, plus at worst the additional cost of crossing into the next car (since you can't put the toilet between two cars, there's a slight asymmetry).

Perfect, thanks!!

The solution is to permanently couple pairs of the two car types, such that the restroom is in the middle.

Of course, this is exactly equivalent to just making the cars so that they all have restrooms, but are twice as long...

Not exactly equivalent - if you actually made each car twice as long, I think it would reduce the the turning radius of the train.

Two cars were coupled together correctly (i.e. car with toilet coupled on toilet end to a car without a toilet), and then never decoupled. Each two car couple was then treated as a single unit.

how do they solve the issue of the turntables being big enough for only one car at a time?

There's no need to reverse these paired cars; they're bidirectional.

Turntables? Those usually only get used when something (like an engine or motor unit) needs to be turned around. Many motor units that I see can operate just as well without turning around; some have cabins at both ends, or are in mated pair configurations with a "backwards" facing motor unit. Most carriages (that I see on a regular basis) have either half the seats facing one way, and half the other, or are reversible.

Regular switching track suffices to switch which end of a train a motor units runs on, and some smaller passenger trains can work fine in "push" instead of "pull" mode.