Here's Hangman Premium in action (I don't believe there's a free ad-supported version for this one):
Picking a category (from a scrolling pane of ten - the others are Countries, Capitals, US States, US Presidents and Animals); (right) a game in progress, you'll be surprised at your own pattern matching skills.
As letters are guessed correctly, they're filled in and shaded in blue in the grid - incorrect guesses are shown in red and the gallows gradually drawn, as usual. And, unlike in the paper version, you can't accidentally guess the same wrong letter twice!
You can buy Hangman Premium for £1 here in the Nokia Store. Yes, the gameplay itself is notoriously simplistic (heck, five year olds can play it), but the focus on specific categories adds extra interest and makes the game less random.
I'd criticise G Soft's code in terms of implementation here, though. As with several other games in their range, the sounds are inconsistent - you can reduce the volume in settings, but some of the sound samples continue to ring out loudly, which is annoying if you're playing on the train or in a family living room.