Perl Weekly Challenge 129: Add Linked Lists

by Abigail


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.

HINT: Just a suggestion, 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.

Example 1

Input: L1 = 1 -> 2 -> 3
       L2 = 3 -> 2 -> 1
Output: 4 -> 4 -> 4

Operation: Pick the first rightmost element of L1 i.e. 3 and adds to the first rightmost element of L2 i.e. 1. Finally store the result i.e. 3 in the new linked list. Move to the next one of both linked lists L1 and L2, perform the same operation. In case the sum >= 10 then you apply the same rule you would do to regular addition problem i.e. divide the sum by 10 keep the remainder and push to the new linked list. Don't forget to carry, 1, to the next operation. In case one linked list is smaller than the other, you can safely assume it is 0.

Example 2

Input: L1 = 1 -> 2 -> 3 -> 4 -> 5
       L2 =           6 -> 5 -> 5
Output:     1 -> 3 -> 0 -> 0 -> 0


  1. 1st member of L1 = 5 and 1st member of L2 = 5
  2. 5 + 5 = 10
  3. 0 pushed to the new linked list.
  4. carry forward 1.
  5. 2nd member of L1 = 4 and 2nd member of L2 = 5
  6. 4 + 5 + 1 (carry) = 10
  7. 0 again pushed to the new linked list.
  8. carry forward 1.
  9. 3rd member of L1 = 3 and 3rd member of L2 = 6
  10. 3 + 6 + 1 (carry) = 10
  11. 0 pushed to the new linked list.
  12. carry forward 1.
  13. 4th member of L1 = 2 and assume 0 as the 4th member of L2 since there are only 3 members.
  14. 2 + 1 (carry) = 3
  15. 3 pushed to the new linked list.
  16. 5th member of L1 = 1 and assume 0 as the 5th member of L2 since there are only 3 members.
  17. 1 + 0 = 1
  18. 1 pushed to the new linked list.

So the new linked list now have: 1 -> 3 -> 0 -> 0 -> 0.

The above suggestion is one way, not necessarily the best way to deal with it.


This challenge had me almost throw up in disgust. Linked list? Seriously? In Perl (and many other modern languagues), most things for which you might want to use a linked list, arrays will work very well. There are some problems for which linked lists work very well, and arrays won't — just take a look at Advent of Code, might manages to construct such a challenge most years.

For this challenge, using linked list is just, uhm, silly to say it mildly. Using linked list to add two numbers is about as useful as writing a novel with using the letter e. (This has been done in the past, but we don't see the top-10 reading list being flooded with e-free novels).

To add insult to the injury, our linked lists run from most significant digit to least, but addition goes from least significant digit to most, meaning we have to process a linked list back to front. How stupid is that?

The Hint

Then there is the hint. Which starts with feel free to come up with your own unique way to deal with the task. And then has a list of things it expects to be done. Which is it? Are we free to come up with our unique way, or are we to do the expected things?

And the things it expects to be done raise questions. We're to take a method which takes a list of numbers, and then returns a list. Right. Useful.

Also, a method to add a new member. But where? At the end? The beginning? In the middle? After a given member, given a pointer to it? The latter is the only useful for linked lists, and about the only reason to use a linked list over an array (and then only if we have tons of elements, and do tons of insertions).

We'll just treat the hint as confusing rubbish, and ignore it.



First, we create two subroutines, n2ll which takes a number, and turns it into a linked list (using recursion), and ll2n, which takes a linked list and turns it into a single number (again, using recursion):

sub n2ll ($num) {$num =~ /./ ? [my $x = $&, n2ll ($')] : []}
sub ll2n ($ll)  {@$ll ? $$ll [0] . ll2n ($$ll [1]) : ""}

Sure, this uses $& and $', which can performance issues, but since we have a use linked lists to add two numbers, we're clearly not interested in performance in anyway.

Next, a method to add the content of two lists, which returns the sum as a linked list. We do this by flatting the lists into numbers, adding them (as big integers), and turning the result into a linked list again. (I just couldn't bother following a 18-step formula which does the work of a 1-character operator):

sub add ($ll1, $ll2) {use bigint; n2ll (0 + ll2n ($ll1) + ll2n ($ll2))}

Now we are ready to read in the data. We assume the input consists of two lines: one number/list per line. This may be given as a number, or in the digit/arrow format from the examples: we ignore anything which isn't a digit:

my $f_ll = n2ll <> =~ s/[^0-9]+//gr;
my $s_ll = n2ll <> =~ s/[^0-9]+//gr;

Add them:

my $sum_ll = add ($f_ll, $s_ll);

And we can now pretty print them by turning the list into a number, splitting that into characters, then joining the characters by arrows:

say join " -> " => split // => ll2n $sum_ll;

Find the full program on GitHub.

Other languages

We won't insult other languages by using linked lists to add numbers.

Please leave any comments as a GitHub issue.