# Write a function that adds two numbers stored in a linked list and returns the sum

Just for fun I did the following exercise from "Cracking the coding interview. 4th edition":

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE Input: (3 -> 1 -> 5), (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

Although my solution it seems to return valid results it is significantly different from the proposed solution. I implemented my own structures and I haven't used recursion.

I know both solutions are valid, but in case of a real interview: How would the interviewer consider my answer? Which caveats should I consider?

public class ex24
{
public static void Run()
{

var n1 = CreateNumber(5, 1, 3);
var n2 = CreateNumber(2, 9, 5);

Figure xF = n1;
Figure xY = n2;
int alpha = 0;

Figure prev = null;
Figure ini;
do
{
int n1v = n1 != null ? n1.Value : 0;
int n2v = n2 != null ? n2.Value : 0;

int sum = n1v + n2v + alpha;

decimal f = sum / (decimal)10;
alpha = (int)f;
sum = (int)((f - alpha) * 10);

if (prev == null)
{
ini = new Figure(sum);
prev = ini;
}
else
{
prev.Next = new Figure(sum);
prev = prev.Next;
}

n1 = n1 != null ? n1.Next : null;
n2 = n2 != null ? n2.Next : null;

} while (n1 != null || n2 != null || alpha != 0);

// Result is stored on 'ini'.

}
public class Figure
{
public Figure Next;
public int Value;

public Figure(int value)
{
this.Value = value;
}

public override string ToString() =>"" + this.Value;

}

public static Figure CreateNumber(params int[] values)
{
Figure ini = new Figure(values[values.Length - 1]);
Figure prev = ini;
for (var ix = values.Length - 2; ix >= 0; ix--)
{
prev.Next = new Figure(values[ix]);
prev = prev.Next;
}

return ini;
}

}

• Why not use the linked list type from the framework (System.Collections.Generic.LinkedList<T>)? – user190892 Feb 10 '19 at 14:32

## 1 Answer

• Strictly speaking, the code does not solve the problem. As an interviewer I'd expect a clearly defined

    List add(List l1, List l2)


method.

At the very least, rename Run to add, and do not CreateNumbers in it, but pass them as parameters.

• Since it is guaranteed that every node contains a digit, the sum may never exceed 19. This means, among other things, that there is no need for decimal. Everything can be done with primitive types, e.g.

    alpha = sum > 10;
sum -= alpha * 10;


As a side note, the entity you call alpha is traditionally called carry.

• The do {} while() approach seems to create more problems than it solves. An immediate manifestation is duplication of n1 != null tests. Consider

    while (n1 != null && n2 != null) {
// addition logic here
n1 = n1.Next;
n2 = n2.Next;
}


and promote the carry along the remainder of the longer list in a separate loop.

• Consider creating a dummy head for a resulting list. It is a standard trick to avoid a special case of prev == null, e.g.

    Figure dummy = new Figure;
Figure tail = dummy;

while (....) {
....
tail.next = new Figure(sum);
tail = tail.next;
}
....
return dummy.next;

• alpha = sum > 10; sum -= alpha * 10 won't work in C# (something like carry = sum / 10; sum -= carry * 10 would). Also worth noting that List is the .NET type which represents a dynamic array, rather than a linked-list (LinkedList) – VisualMelon Feb 10 '19 at 10:10
• On 3rd point. Both numbers might not have the same length so checking for a null value is required, moreover, the while condition has to be an OR instead of AND. – arturn Feb 10 '19 at 18:30
• @arturn The third point explicitly said promote the carry along the remainder of the longer list in a separate loop. True, I didn't spell out this separate loop, pretty much intentionally. – vnp Feb 10 '19 at 18:48
• @vnp Sure ;) Sorry,I misunderstood the sentence! – arturn Feb 13 '19 at 9:40