Here is yet another solution. This one has a single loop and no recursion.

#!/usr/local/bin/perl
use strict;
use warnings;
use Data::Dumper;

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


my %hh;
my %tails;

while(my ($key, $value) = each %$h) {
    my $val;
    if($value == -1) {
        $val = -1;
    } elsif(exists($hh{$value})) {
        $val = { $value => $hh{$value} };
        delete($hh{$value});
    } else {
        $val = {};
        $tails{$value} = $val;
    }
    if(exists($tails{$key})) {
        $tails{$key}{$key} = $val;
    } else {
        $hh{$key} = $val;
    }
}

print Dumper(\%hh);
[download]