Task — Add linked lists

You are given two linked lists containing 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.

Examples

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
    Operations:
    a) 1st member of L1 = 5 and 1st member of L2 = 5
    b) 5 + 5 = 10
    c) 0 pushed to the new linked list.
    d) carry forward 1.
    e) 2nd member of L1 = 4 and 2nd member of L2 = 5
    f) 4 + 5 + 1 (carry) = 10
    h) 0 again pushed to the new linked list.
    i) carry forward 1.
    j) 3rd member of L1 = 3 and 3rd member of L2 = 6
    k) 3 + 6 + 1 (carry) = 10
    l) 0 pushed to the new linked list.
    m) carry forward 1.
    n) 4th member of L1 = 2 and assume 0 as the 4th member
       of L2 since there are only 3 members.
    o) 2 + 1 (carry) = 3
    p) 3 pushed to the new linked list.
    q) 5th member of L1 = 1 and assume 0 as the 5th member
       of L2 since there are only 3 members.
    r) 1 + 0 = 1 #
    s) 1 pushed to the new linked list.
    So the new linked list now has: 1 -> 3 -> 0 -> 0 -> 0.
    The above suggestion is one way, not necessarily the
	best way to deal with it.

Analysis

This is a rather complicated explanation of what is required! Consider the following:

     12345
      +655
     -----
     13000

This is the essence of example 2 above, with each of the three numbers in the sum expressed as a linked list.

I have kept the logic of example 2, keeping the numbers as linked lists, though it may be simpler and easier to understand if we convert L1 and L2 to conventional numbers, add them together and convert the result back to a linked list.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2021-09-06
# Perl weekly challenge 129 task #2

use utf8;
use v5.26;
use strict;
use warnings;

my ($L1, $L1_left, $L2, $L2_left, $L3, $one, $two, $carry, $sum, $units, $blanks1, $blanks2);

# given lists
$L1 = $L1_left =      '9 -> 2 -> 0 -> 0 -> 5 -> 0 -> 7 -> 0';
$L2 = $L2_left = '7 -> 9 -> 9 -> 0 -> 8 -> 3 -> 9 -> 7 -> 0';

# cycle back from the end of each list
$carry = 0;
$L3 = '';
while ($L1_left =~ m|\d| or $L2_left =~ m|\d| or $carry) {   # not finished yet
    $one = $two = 0;
    ($L1_left, $one) = ($1, $2) if $L1_left =~ m|(.*)(\d)|;  # strip off last (remaining) digit of each list
    ($L2_left, $two) = ($1, $2) if $L2_left =~ m|(.*)(\d)|;
    $sum = $one + $two + $carry;                      # add the two digits and any carryover
    $units = $sum % 10;                               # get new digit     
    $L3 = "$units -> $L3";                            # add it to the start of L3
    $carry = ($sum - $units) / 10;                    # and compute any carryover (can only be 0 or 1)
}

# line them up
$L3 =~ s|....$||;     # remove final ' -> '
$blanks1 = length($L3) - length($L1);
$blanks2 = length($L3) - length($L2);
print 'L1 = ' . (' ' x $blanks1) . $L1 . "\n" .
      'L2 = ' . (' ' x $blanks2) . $L2 . "\n" .
      "L3 = $L3\n";

Output

L1 =      9 -> 2 -> 0 -> 0 -> 5 -> 0 -> 7 -> 0
L2 = 7 -> 9 -> 9 -> 0 -> 8 -> 3 -> 9 -> 7 -> 0
L3 = 8 -> 9 -> 1 -> 0 -> 8 -> 9 -> 0 -> 4 -> 0