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

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

sub LEAF() { -1 }


# Make a list of toplevel keys: values occurring once and not LEAF
my %tl;
++$tl{$_} for  grep { $_ != LEAF }  %$h ;
my @toplevel =  grep { $tl{$_} == 1 } keys %tl;


# Build linked lists from head as HoHo...
my %answer = ();
for my $k ( @toplevel ) {
    my $cursor = \%answer;
    $cursor->{$k} = $h->{$k};

    while ( LEAF != ( my $next_k = $cursor->{$k})  ) {
        $cursor = $cursor->{$k} =  { $next_k, $h->{ $next_k } };
        $k = $next_k;
    }
}

print Dumper \%answer;
[download]