Book I read 20 years ago... - a race of shapeshifters trapped underground

[ajanders]

Somewhere in the book the group travels through an underground race of shapeshifters where they are trapped and aren't allowed to leave unless one of them stays to repopulate their race (one of them does happily). Near the end it's something like stepping from planet to planet in a race against time or something. I am fearful that those two parts I remember may be from two different books but I think it's from the same one. Help me, it's killing me!