blob: 6767dbe0617e451aafc6e1175a56a6e86a14b86b (
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
|
#!/usr/bin/perl
use strict;
use warnings;
use LinkedList::Single;
# Print the node data from a linked list.
sub list_print {
my $list = shift;
for ($list->head; $list->has_next; $list->next) {
print $list->node_data->[0], " -> ";
}
print $list->node_data->[0], "\n"
}
# Remove n-th last element from the list.
sub remove_from_end {
my ($list, $n) = @_;
# Create a new singly linked list that will hold at most $n
# "position pointers" into the original list.
# The root node is special and is stored in the new
# list's first node.
my $record = LinkedList::Single->new($list->root_node);
my $len = 1;
# Process all nodes but the last from the original list.
for ($list->head; $list->has_next; $list->next) {
# Record the position.
$record->push($list->node);
# Discard the first recorded position if the maximum length
# is exceeded.
$record->shift if ++$len > $n;
}
# Retrieve the cut-node position from the first node of the record
# list, reposition the original list and cut the next node.
# If $n is large enough, the root_node is still the first node
# of the record list causing the first node of the original list
# to be cut.
$list->node($record->head->node_data->[0]);
$list->cut;
$list;
}
my $L = 5;
for my $N (1 .. 6) {
my $list = LinkedList::Single->new(1 .. $L);
if ($N == 1) {
print "List:\n";
list_print $list;
}
print "N=$N\n";
list_print remove_from_end $list, $N;
}
|
