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

Question

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;
    }

}

Answer 1

• 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;