Calculating the sum of values ​​in a linked list

Question

I recently got a programming question.

There are 2 linked lists. Each node stores a value from 1 to 9 (indicating one index 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)

which will return the sum of the values ​​in 2 related list arguments.

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

And array b: 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 these values.

Here is the code: it works with O (n) complexity, as I assume. Once through each of the inputs of the array and once to create an output array.

Any improvements? Improved 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

Other solutions that I saw for this problem are related to gradually increasing the returned list, iterating back over both input lists at the same time as adding each item when moving to a new list. This method is more complicated because you need to add each element and handle the transfer.

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

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

Iterate back

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

carry 1

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

carry 1

(1) + 2 + 6 = 9 (returned list = 9 → 1 → 2)

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

You can implement this using Stacks to get the nature of LIFO in the opposite direction if the list is only linked separately.

Answer 2

Hi @rtindru : As you said you want to add two linked lists. First linked list a: 1->2->3->4 Second linked list b: 5->6->7->8

The question does not mention that the numbers stored in the linked list are stored in the same order or in reverse order as the number appears. The first approach is more complicated.

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 the number is stored in reverse order, then

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

The question you are asking for the first approach, and this example also applies to the first approach, but the source code for the second approach. Please agree with him.

Answer 3

The other answers I've seen often rely on an extra stack. In fact, it can be solved only with the additional space O(1) . 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 simply iterate over both lists, store the values ​​of the current values ​​in a and b in the value of the new list c . But we cannot just take the sum of the two values ​​as the value in c , because if the two lists differ in length, we could not restore the original values ​​in the list a and b . A little trick is to generate a two-digit value, the first digit is the value in a , and the second value in b , for example:

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

When the list c completely created, we rewind the pointer "p1". First, we divide the two numbers in node by the pointer "p2", then add the right number to the value in p1. Then we cancel p1 and set p1->next , p2 and p2->next , and then go to the previous nodes.

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

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

Answer 4

Here is my answer to this question (C # is used instead of Java, but the logic can be easily replicated in any language). I used backward list binding for direct summation, and for backward storage, I used the forward wrap method.

 /* 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 5

You can do this by changing the link binding. This is a C # implementation and this is 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; }