Hi all. I only completed one challenge this week. But at 140 lines, it's the second longest submission. For the record, my longest submission was 156 lines for challenge 118.
You are given two linked list having single digit positive numbers.
Write a script to add the two linked list and create a new linked representing the sum of the two linked list numbers. The two linked lists may or may not have the same number of elements.
Feel free to come up with your own unique way to deal with the task. I am expecting a class representing linked list. It should have methods to create a linked list given list of single digit positive numbers and a method to add new member. Also have a method that takes 2 linked list objects and returns a new linked list. Finally a method to print the linked list object in a user friendly format.
As regularly readers of my blog probably know, I don't like to use non-core modules when solving the challenge. And that is true this time.
It's also the first time I've done a linked list challenge properly. So the main part of the challenge is to write the LinkedList module. Since we need to know the values in reverse, this is a double linked list. That is, each node is linked both the next and previous node. In the real world, I would have used Moo, but see the above paragraph for why I didn't.
My LinkedList module stores an internal value of
_list that contains the ordered list of LinkedList::Node objects. It has the
last method which returns the first and last node respectively. And it has the
as_string function to display the list as a printable string separated by
Each LinkedList::Node object has the methods
value (to get the value of the node), and
next to get the previous or next node (or undef if none exists). It also has
set_next to set these values.
That's all the boring bits. Now for the fun.
The LinkedList model has the methods
unshift which both do the same as the Perl methods of the same name. These methods create a new node object, and creates the prev / next link between the last node and the newly created one (or the first node for the unshift method).
The LinkedList module also has the
_add method, which overloads the addition method. For this method, I get the last value of each linked list and sum them together. The last digit is added to the
$new_list linked list, and the carry forward is added to the
$carry variable. I repeat this until both lists are exhausted and there is no carry forward.
Still reading? Well done :-)
$ ./ch-2.pl 123 321 4 -> 4 -> 4 $ ./ch-2.pl "1 -> 2 -> 3 -> 4 -> 5" "6 -> 5 -> 5" 1 -> 3 -> 0 -> 0 -> 0