How to find broken symbolic links (aka. symlinks)

I've seen many tips on how to find broken symbolic links in a directory tree, but most of them fail in case of directories with the sticky bit enabled.

The two most popular approaches use find and optionally test:
  • find -L dirname -type l -ls
  • find dirname -type l | (while read FN ; do test -e "$FN" || ls -ld "$FN"; done)
However both fail for symbolic links that were created in a directory that has the sticky bit enabled.
Eg. symlinks in /tmp

The problem is that both approaches fail (you get a "permission denied" message) -even executing it with root priveleges- if the sticky bit is set on the parent directory and the symlink was not created by the user executing the given search command.
Using readlink you can avoid this:
find dirname -type l -not -exec sh -c 't="$(readlink "{}" 2> /dev/null)" && [ -n "$t" -a -e "$t" ]' \; -ls

Unfortunately the above example code is extremely inefficient since find has to execute a shell and the shell has to execute readlink for each symlink. A lot faster implementation of the same idea is to use Perl:
find dirname -type l -print | perl -nle 'use File::Basename; $f = readlink; $a = substr($f, 0, 1) eq "/"; !$a && -e dirname($_) . "/" . $f || $a && -e $f || print "$_ -> ", $f'