blob: a340f898e9aca07164f93f94f3abf74701badba8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
use strict;
use warnings;
package LinkedList{
use boolean;
use Tie::RefHash;
use Class::Struct;
package Node{
use Class::Struct;
struct(
data => q/$/,
next => q/Node/
);
}
struct(
head => q/Node/
);
sub stringify{
my($self) = @_;
my $s = "";
my $next = $self->head()->next();
while($next && $next->next()){
$s .= " -> " if $s;
$s = $s . $next->data();
$next = $next->next();
}
$s = $s . " -> " . $next->data() if $next->data();
$s .= "\n";
return $s;
}
sub insert{
my($self, $data, $previous) = @_;
if(!$previous){
$previous=new Node(data => undef, next => undef);
$self->head($previous);
}
my $next=new Node(data => $data, next => undef);
$previous->next($next);
return $next;
}
sub partition{
my($self, $k) = @_;
my $previous = $self->head();
my $next = $self->head()->next();
tie my %node_value, "Tie::RefHash";
while($next){
if($next->data() < $k){
$node_value{$next} = $next->data();
if($next->next()){
$previous->next($next->next());
}
else{
$previous->next(new Node());
$next = undef;
next;
}
}
$previous = $next;
$next = $next->next();
}
my @sorted_nodes = sort {$node_value{$b} <=> $node_value{$a}} keys %node_value;
$previous = $self->head();
my $old_first = $previous->next();
while(@sorted_nodes){
my $node = pop @sorted_nodes;
$previous = insert($self,$node->data(), $previous);
}
$previous->next($old_first);
}
true;
}
|
