**Advent Calendar 2020**

### | **Day 9** | **Day 10** | **Day 11** |

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.

**NOTE:** Please use pure linked list implementation.

## Example

##### Given Linked List: 1 -> 2 -> 3 -> 4 -> 5

##### when $N = 1

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

##### when $N = 2

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

##### when $N = 3

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

##### when $N = 4

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

##### when $N = 5

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

##### when $N = 6

##### 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;
my $head = Node->new(undef);
make_list($head, 1..5);
print_list($head);
remove_from_end($head, $N);
print_list($head);
```

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

```
sub make_list($head, @a) {
my $node = $head;
for my $i (@a) {
$node->set_next(Node->new($i));
$node = $node->next;
}
}
sub print_list($head) {
my $node = $head->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 $node = $head;
my $len = 0;
while (defined $node->next) {
$len++;
$node = $node->next;
}
return $len;
}
sub remove_from_end($head, $n) {
# get to the position before the node to delete
my $pos = list_length($head);
my $node = $head;
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.