blob: 9c8bc10facffc3da740451f0230ade6adad42de5 (
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#!/usr/bin/perl
use strict;
use warnings;
use LinkedList::Single;
sub list_zip;
sub list_reverse;
sub list_halve;
# Reorder list according to challenge #2.
#
# At first glance the expensive "pop" operation seems to be required
# for this task, but actually it isn't.
sub list_reorder {
my $list = shift;
list_zip $list, list_reverse list_halve $list;
}
# Split list in two (around the middle) with a larger leading part.
sub list_halve {
my $list = shift;
# Count the length of the list.
my $length = 0;
for ($list->head; $list->has_next; $list->next) {
$length++;
}
# Advance to the middle of the list.
$list->head;
for (my $i = 0; 2 * $i < $length; $i++) {
$list->next;
}
# Splice off and return the trailing part.
$list->splice(int($length / 2));
}
# Reverse list.
sub list_reverse {
my $list = shift;
# Seek to the last node and count the length.
my $length = 0;
for ($list->head; $list->has_next; $list->next) {
$length++;
}
# Move leading nodes one by one from the head straight after
# the (former) last node.
$list->add($list->shift) while $length--;
$list;
}
# Merge two lists one by one.
sub list_zip {
my ($first, $second) = @_;
# Remove node from the head of the second list and add it at
# the current position of the first list. Then skip over
# the newly added node and the next node of the first list.
$first->head;
$second->head;
$first->add($second->shift)->next->next while !$second->is_empty;
$first;
}
# Generate a linked list containing numbered nodes.
sub list_gen {
my ($id, $count) = @_;
LinkedList::Single->new(map [$id, $_], (1 .. $count));
}
# Print node data from linked list.
sub list_print {
my ($label, $list) = @_;
local $" = '';
print "$label:\t";
for ($list->head; $list->has_next; $list->next) {
print "@{$list->node_data->[0]} -> ";
}
print "@{$list->node_data->[0]}\n";
}
# main
# Some examples.
for my $length (3 .. 8) {
my $list = list_gen 'n', $length;
list_print 'orig', $list;
list_reorder $list;
list_print 'reord', $list;
print "\n";
}
|
