Hmm, I don't remember this being the case but from watching some YouTube videos it seems that it works like this in the N64 version:
The Crow's Nest battle immediately follows the Prison Ship level when played for the first time. However, when you stop playing/exit to the Hall of Doors during the Crow's Nest battle or when revisiting the level, you can go straight to the Crow's Nest level without playing the Prison Ship again.