I would not worry about efficiency. This is for a home-brew, one-off battery charger, not a cell phone. I think the complexity and cost of getting a switching regulator to work correctly far outweighs the little bit of heat saved. The LM317 is a power device; it can take the heat. When you have real numbers for the transformer-bridge-filter capacitor section, working out the heatsink required is simple math.
Schematics #1 and #3 are constant current circuits, which is the right place to start. Schematic #16 adds a form of fully-charged detection to back off the available energy and not overcharge (overstress) the battery chemistry, but is not constant current for the main charging cycle.
Note that Linear Tech, Maxim, and TI (formerly Unitrode) make chips designed specifically for "proper" charging of battery chemistries, if you want to go that route. If not ...
#21 is better, but not quite there. For semi-intelligent charging on the cheap, I like the two LM317's in series. The first is a standard constant-voltage regulator to set the maximum possible voltage across the battery when it is fully charged. The second is a constant current regulator to set the maximum possible current to the battery during the heavy part of the charging cycle. In your schematic, IC1 needs the two standard voltage-setting resistors, with the thermistor circuit added in parallel with the lower one. Depending on the thermistor, you might be able to simply place it in parallel with the shunt resistor, but that way might not have enough protection effect. That is, when the battery gets hot it might not turn down the output voltage enough.
ak