my %mapping; @mapping{@list} = 1..@list;

my @rearranged =
  map { $_->[0] }
  sort { $a->[1] <=> $b->[1] or $a->[0] cmp $b->[0] }
  map { [$_, $mapping{substr($_,0,1)} || 0] } @list2;