This could probably be simplified a little:

#! perl -sw
use strict;
use Data::Dump qw[ pp ];

my $h= {
    (4,-1),
    (2,6),
    (6,4),
    (3,5),
    (5,-1),
    (99,-1),
};

my %invert;
push @{ $invert{ $h->{ $_ } } }, $_ for keys %{ $h };

my %hh;
for( @{ $invert{ -1 } } ) {
    my $ref = { $_, -1 };
    while( exists $invert{ $_ } ) {
        my $key = pop @{ $invert{ $_ } };
        $ref = { $key, $ref };
        delete $invert{ $_ } unless @{ $invert{ $_ } };
        $_ = $key;
    }
    my( $key, $value ) = each %$ref;
    $hh{ $key } = $value;
}

pp \%hh;
__END__
c:\test>755232
{ 
    2 => { 6 => { 4 => -1 } }, 
    3 => { 5 => -1 }, 
    9 => -1 
}
[download]