DEV Community

loading...

Weekly Challenge 129

Simon Green
・3 min read

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.

I attended PyConline Australia the past few days, virtually of course thanks to the 'rona. The videos from the conference should be on their Youtube channel by the time you read this.

This weeks challenge and my solution.

TASK #2 › Add Linked Lists

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.

My solution

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 first and 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 prev and next to get the previous or next node (or undef if none exists). It also has set_prev and set_next to set these values.

That's all the boring bits. Now for the fun.

The LinkedList model has the methods push, 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 :-)

Examples

$ ./ch-2.pl 123 321
4 -> 4 -> 4

$ ./ch-2.pl "1 -> 2 -> 3 -> 4 -> 5" "6 -> 5 -> 5"
1 -> 3 -> 0 -> 0 -> 0
Enter fullscreen mode Exit fullscreen mode

Discussion (0)