Calculating the Sum of values in a linked list

Question

I got a programming question at an interview recently.

There are 2 linked lists. Each node stores a value from 1 through 9 (indicating one index of the number). Hence 123 would be a linked list 1->2->3

The task was to create a function:

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)

that would return the sum of the values in the 2 linked list arguements.

If the array a is: 1->2->3->4

And the array b is: 5->6->7->8

The answer should be: 6->9->1->2

Here is my algorithm:

Go through each node in a and b, get the values as an integer and add them. Create a new linked list with the those values.

Here is the code: It runs with a complexity of O(n) roughly I assume. Once through each of the array inputs and once to create the output array.

Any improvements? Better algorithms... or code improvements

public class LinkedListNode {
        LinkedListNode next;
        int value;

    public LinkedListNode(int value) {
        this.value = value;
        this.next = null;
    }

    static int getValue(LinkedListNode node) {
        int value = node.value;
        while (node.next != null) {
            node = node.next;
            value = value * 10 + node.value;
        }
        return value;
    }

    static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) {
        LinkedListNode answer = new LinkedListNode(0);
        LinkedListNode ans = answer;
        int aval = getValue(a);
        int bval = getValue(b);
        int result = aval + bval;
        while (result > 0) {
            int len = (int) Math.pow((double) 10,
                    (double) String.valueOf(result).length() - 1);
            int val = result / len;
            ans.next = new LinkedListNode(val);
            ans = ans.next;
            result = result - val*len;
            }    
        return answer.next;
    }
}

Answer 1

You can do it by reversing the linkedlists. This is a c# implementation and it's O(n).

    public LinkedList ElementSum(LinkedList other)
    {
        LinkedList linkedListSum = new LinkedList();
        this.Reverse();
        other.Reverse();
        Node n1 = this.head, n2 = other.head;
        int toAdd = 0, carryOver = 0;
        while ((n1 != null) || (n2 != null))
        {
            int num1 = (int) (n1 == null ? 0 : n1.NodeContent);
            int num2 = (int) (n2 == null ? 0 : n2.NodeContent);
            toAdd = (num1 + num2 + carryOver) % 10;
            carryOver = (int)(num1 + num2 + carryOver) / 10;
            linkedListSum.Add(toAdd);
            n1 = (n1 == null ? null : n1.Next);
            n2 = (n2 == null ? null : n2.Next);
        }
        this.Reverse();
        other.Reverse();
        linkedListSum.Reverse();
        return linkedListSum;
    }

Answer 2

Here's my answer to this question (used C# instead of Java but the logic can be replicated easily in either language). I used linked list reversal for forward summing while for reverse storage, I used the carry forward approach.

/*  Program: Given two numbers represented in a linked list in reverse order, sum them and store the result in a third linked list
 *  
 *  Date: 12/25/2015
 */

using System;

namespace CrackingTheCodingInterview
{
    /// <summary>
    /// Singly Linked List with a method to add two numbers stored in two linked lists in reverse order
    /// </summary>
    public partial class SinglyLinkedList
    {
        /// <summary>
        /// Adding two numbers stored in a linked list in reverse order
        /// </summary>
        /// <param name="num1">Linked List 1 storing number 1</param>
        /// <param name="num2">Linked List 2 storing number 2</param>
        /// <param name="result">Linked List 3 storing sum of number 1 and number 2</param>
        public static void SumNumbersReverse(SinglyLinkedList num1, SinglyLinkedList num2, SinglyLinkedList result)
        {
            int carryForward = 0;
            int sum = 0;

            Node num1Digit = num1.head;
            Node num2Digit = num2.head;

            int sum1 = 0;
            int sum2 = 0;

            while (num1Digit != null || num2Digit != null)
            {
                if (num1Digit == null)
                {
                    sum1 = 0;
                }
                else
                {
                    sum1 = (int)num1Digit.Data;
                }

                if (num2Digit == null)
                {
                    sum2 = 0;
                }
                else
                {
                    sum2 = (int)num2Digit.Data;
                }

                sum = sum1 + sum2 + carryForward;

                if (sum > 9)
                {
                    carryForward = 1;
                }
                else
                {
                    carryForward = 0;
                }

                result.Insert(sum % 10);

                if (num1Digit != null)
                {
                    num1Digit = num1Digit.Next;
                }

                if (num2Digit != null)
                {
                    num2Digit = num2Digit.Next;
                }
            }

            result.ReverseList();
        }

        /// <summary>
        /// Adding two numbers stored in a linked list in reverse order
        /// </summary>
        /// <param name="num1">Linked List 1 storing number 1</param>
        /// <param name="num2">Linked List 2 storing number 2</param>
        /// <param name="result">Linked List 3 storing sum of number 1 and number 2</param>
        public static void SumNumbersForward(SinglyLinkedList num1, SinglyLinkedList num2, SinglyLinkedList result)
        {
            num1.ReverseList();
            num2.ReverseList();

            SumNumbersReverse(num1, num2, result);

            result.ReverseList();
        }

        /// <summary>
        /// Reverse a singly linked list
        /// </summary>
        public void ReverseList()
        {
            Node prev = null;
            Node curr = head;
            Node currNext;

            while(curr != null)
            {
                currNext = curr.Next;
                curr.Next = prev;
                prev = curr;
                curr = currNext;
            }

            head = prev;
        }
    }


    internal class SumNumbersLinkedListTest
    {
        static void Main()
        {
            SinglyLinkedList num1 = new SinglyLinkedList();
            SinglyLinkedList num2 = new SinglyLinkedList();

            num1.Insert(6);
            num1.Insert(1);
            num1.Insert(7);

            num2.Insert(2);
            num2.Insert(9);
            num2.Insert(5);

            num1.Print();
            num2.Print();

            SinglyLinkedList resultReverseSum = new SinglyLinkedList();
            SinglyLinkedList resultForwardSum = new SinglyLinkedList();

            SinglyLinkedList.SumNumbersReverse(num1, num2, resultReverseSum);
            Console.WriteLine("After summing reverse: ");
            resultReverseSum.Print();

            SinglyLinkedList num3 = new SinglyLinkedList();
            SinglyLinkedList num4 = new SinglyLinkedList();

            num3.Insert(7);
            num3.Insert(1);
            num3.Insert(6);

            num4.Insert(5);
            num4.Insert(9);
            num4.Insert(2);

            SinglyLinkedList.SumNumbersForward(num3, num4, resultForwardSum);
            Console.WriteLine("After summing forward: ");
            resultForwardSum.Print();

            Console.ReadLine();
        }
    }
}

Answer 3

Hi @rtindru: As you told that you want to add two linked list. The first linked list a is: 1->2->3->4 The second linked list b is: 5->6->7->8

In the question it is not mentioned that digits stored in the linked list is store in same order or reverse order as the number is appeared. First approach is more difficult.

First Approach:

list a: 1234
list b: 5678

The answer should be: 6->9->1->2

   1 2 3 4
+  5 6 7 8
-----------------
   6 9 1 2

Second Approach

If number is stored in the reverse order then

First linked list a is: 1->2->3->4. Actual number: N1=4321. And the second linked list b is: 5->6->7->8. Actual number: N2=8765. Sum will be 6->8->0->3->1. This is the easy approach.

In the question you are asking for First Approach and given example is also for first approach but your source code is for second approach. Please conform it.

Answer 4

Other answers I saw often rely on an extra stack. Actually it can be solved with only O(1) extra space. I modified the example in another answer to make the two lists different in length:

list a is: 1->2->3->4
list b is: 5->6->7->8->3->6

We can just iterate both lists, store the values of the current values in a and b, in the value of the new list c. But we cannot simply take the sum of the two values as the value in c, because in case the two lists are different in length, we couldn't recover the original values in list a and b. A little trick is to generate a two-digit value, the first digit being the value in a, and the second the value in b, like:

list c: 15 <- 26 <- 37 <- 48 <- 3 <- 6
                                     ^ pointer "p1"
                           ^ pointer "p2" here to mark the end of list a

Once list c is fully created, we rewind from pointer "p1". We first separate the two numbers in the node at pointer "p2", then add the right number to the value at p1. Then we reverse p1 and set p1->next, and p2 and p2->next, and then proceed to the previous nodes.

list c: 15 <- 26 <- 37 <- 8 <- 3 -> 4
                               ^ p1
                     ^ p2
                               carry = 1

The time complexity is 2*max( length(a), length(b) ).

Answer 5

Other solutions I have seen for this problem involve building the returned list incrementally by iterating backwards over both the input lists at the same time adding each element as you go to a new list. That way is more complicated because you have to add each element and deal with carry overs.

If the array a is: 1->2->3->4

And the array b is: 5->6->7->8

Iterate backwards

Then 4 + 8 = 12 (returned list current = 2)

carry the 1

(1) + 3 + 7 = 11 (returned list = 1-> 2)

carry the 1

(1) + 2 + 6 = 9 (returned list = 9 -> 1 ->2 )

1 + 5 = 6 ( return list = 6->9>1->2)

You can implement this by using Stacks to get the LIFO nature to iterate backwards if the list is only singly linked.