blob: f9bbf97102375c9d4f6403c76dad66423288bddf (
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
|
#!/usr/bin/perl
# expects split limit in $ARGV[0]
# expects values to build linked list from in @ARGV[1..-1]
use strict;
use warnings;
# create linked list from given array ref
sub make_list {
my $values = shift;
my $head = {};
my $prev = $head;
foreach my $val (@$values) {
my $this;
$this->{val} = $val;
$prev->{next} = $this;
$prev = $this;
}
return $head->{next};
}
# print linked list from given title and head ref
sub print_list {
my ($title, $head) = @_;
print $title, ":\t";
for (my $this = $head; $this; $this = $this->{next}) {
print $this->{val};
print '->' if $this->{next};
}
print "\n";
}
# switch list
# limit given as 1st arg,
# linked list given by head ref in 2nd arg
# returns: ref to head of switched list
sub switch_list {
my ($lim, $head) = @_;
my $upper = {};
my $uhead = $upper;
my $lower = {};
my $lhead = $lower;
for (my $this = $head; $this; $this = $this->{next}) {
if ($this->{val} < $lim) {
$lower->{next} = $this;
delete $upper->{next};
$lower = $this;
} else {
$upper->{next} = $this;
delete $lower->{next};
$upper = $this;
}
}
# invalidate old head ref
undef $_[1];
if ($lhead->{next}) {
$lower->{next} = $uhead->{next};
return $lhead->{next};
} else {
return $uhead->{next};
}
}
# main
my $splitval = shift;
my $head = make_list \@ARGV;
print_list 'original', $head;
my $switched = switch_list $splitval, $head;
print_list 'switched', $switched;
|
