## Advent Calendar - December 10, 2020

Friday, Dec 18, 2020| Tags: Perl

The gift is presented by Walt Mankowski. Today he is talking about his solution to the task `Trim Linked List` of “The Weekly Challenge - 071”. This is re-produced for Advent Calendar 2020 from the original post by Walt Mankowski.

You are given a singly linked list and a positive integer `\$N` (>0).

Write a script to remove the `\$Nth` node from the end of the linked list and print the linked list.

If `\$N` is greater than the size of the linked list then remove the first node of the list.

## Example

##### Output: 2 -> 3 -> 4 -> 5

In this task we needed to create a singly linked list, delete the Nth element from the end, and then print the list.

There were also linked lists in Challenge 68 and I was able to reuse the linked list class without any modification.

``````package Node;

use strict;
use warnings;
use feature qw(:5.32);
use experimental qw(signatures);

sub new(\$package, \$val) {
my \$self = {};
bless \$self, \$package;

\$self->{val} = \$val;
\$self->{next} = undef;

return \$self;
}

sub set_next(\$self, \$node) {
\$self->{next} = \$node;
}

sub next(\$self) {
return \$self->{next};
}

sub val(\$self) {
return \$self->{val};
}

1;
``````

My top-level code was quite simple:

``````my \$N = shift @ARGV;

``````

Having an extra node at the beginning makes creating and printing the list easy:

``````sub make_list(\$head, @a) {
for my \$i (@a) {
\$node->set_next(Node->new(\$i));
\$node = \$node->next;
}
}

while (defined \$node) {
print \$node->val;
print " -> " if defined \$node->next;
\$node = \$node->next;
}
say "";
}
``````

Removing the Nth element from the end is trickier though; since we need to use a singly-linked list we can’t go backwards. I chose to solve it by making 2 passes through the list. First I make a full pass to count how many elements are in the list. Then I start back at head and go forward until I’m N+1 elements from the end. Finally I remove the Nth node by linking the N+1th node to the N-1th node.

``````sub list_length(\$head) {
my \$len = 0;
while (defined \$node->next) {
\$len++;
\$node = \$node->next;
}
return \$len;
}

# get to the position before the node to delete
while (\$pos > \$n) {
\$node = \$node->next;
\$pos--;
}

# remove it
\$node->set_next(\$node->next->next);
}
``````

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.