I have bunch of paths. How do I know for example if there is a link in the path?

You won't know from just looking at the string. You'll have to check the filesystem, and for each pathname break it down into its components, using e.g. -l on each one. You can break down a filename using e.g. splitdir from File::Spec, or IMO a little easier, Path::Class. Maybe something like:

use warnings;
use strict;
use Path::Class qw/file dir/;

my $file = file('/tmp/foolink/bar/quz');

my $prev;
while (1) {
    die "doesn't exist: $file" unless -e $file;
    print $file, " is a ", -l $file ? 'link to '.readlink($file)
        : -f $file ? 'file' : -d _ ? 'dir' : 'special', "\n";
    $prev = $file;
    $file = $file->parent;
    last if $prev eq $file;
}

__END__

/tmp/foolink/bar/quz is a file
/tmp/foolink/bar is a dir
/tmp/foolink is a link to foo
/tmp is a dir
/ is a dir
[download]

Update: Added a check to the above code to make sure the file exists in the first place.

Oh I see! I like it! Is there a way to iterate the other way around (from the start of the path to the end instead from the end to the start)? It will be easier to insert the paths into the hash that way.
Also, does it know how to handle with multi-links? For example a/b -> c/d -> e/f? In case it's a link, should I iterate until I get the actual path?

Is there a way to iterate the other way around (from the start of the path to the end instead from the end to the start)?

Sure, Path::Class::Dir's components will give you the filename split into its components, like File::Spec's splitdir that I mentioned above. Note that I'm assuming you're talking about *NIX systems, where the two behave the same, I'm not sure at the moment how they behave in respect to volume names on Windows or other OSes.

Update: You've edited your node to add the following. Please see "It is uncool to update a node in a way that renders replies confusing or meaningless" in How do I change/delete my post? and mark your updates as such.

Also, does it know how to handle with multi-links? For example a/b -> c/d -> e/f? In case it's a link, should I iterate until I get the actual path?

You seem to be asking about readlink, which only reads the target of the link you're asking it to, it won't follow chains of links. You'll either have to do that manually, which is a little tricky (see e.g. my script relink), or if you just want to know the final target, use Cwd's abs_path.