Category: Data Structure And Algorithms Tags:

Two given numbers below represented by linked lists:

9 -> 9 -> 9 -> 9 (9999)

5 -> 5 (55)

1 -> 0 -> 0 -> 5 -> 4 (10054)

 Like 0 People Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 140 Questions: 12 Given Best Solutions: 12 * If we have to add two numbers on paper we do like:

9999

+0055

------------

10054

So in linked list if two are having same length then we can add simply else we have to add prefix of zero's before smaller one to make them same length then we can use recursion to go to the end of both and start adding them.

Node structure:

```public class Node
{
public Node() { }
public Node(int key, Node node)
{
Key = key;
Next = node;
}
public int Key { get; set; }
public Node Next { get; set; }
}```

To get length of a list:

```public static int GetLinkedListLength(Node node)
{
int i = 0;
while (node != null)
{
node = node.Next;
i++;
}
return i;
}```

```public static Node AddPrefix(Node numberNode, int prefixLength)
{
Node prefix = new Node();
Node temp = prefix;
//adding prefix of zero to smaller one, as many as difference in both of list
while (prefixLength != 1)
{
temp.Key = 0;
temp.Next = new Node();
temp = temp.Next;
prefixLength--;
}
temp.Next = numberNode;
numberNode = prefix;
return numberNode;
}```

```public static void PrintList(Node node)
{
while (node != null)
{
Console.Write(node.Key);
node = node.Next;
}
}```

```public static int Sum(Node number1, Node number2, Node sum)
{
int carry = 0;
if (number1.Next != null)
{
sum.Next = new Node();
//recursion
carry = Sum(number1.Next, number2.Next, sum.Next);
}

sum.Key = number1.Key   number2.Key   carry;
//returns carry if sum is more than 9
carry = sum.Key / 10;
//setting remindar to node value
sum.Key = sum.Key - carry * 10;
//returns carry
return carry;
}```

Calling all above from main method:

```static void Main(string[] args)
{
//representing two numbers 9999 and 55
Node number1 = new Node(9, new Node(9, new Node(9, new Node(9, null))));
Node number2 = new Node(5, new Node(5, null));
Node sum = new Node();
//length of numbers
int difference = len1 - len2;
//if number1 is bigger than number2 than prefix of 0 has to be added in number2
//55 will become 0055 so easy to add:
// 9999
// 0055
//-----
//10054

//if not same length making them same length by adding prefix of zero's
if (difference > 0)
else if (difference < 0)
number1 = AddPrefix(number1, difference * -1);

int carry = Sum(number1, number2, sum);
if (carry > 0)
{
Node node = new Node(carry, sum);
sum = node;
}
PrintList(number1);
Console.Write(" + ");
PrintList(number2);
Console.Write(" = ");
PrintList(sum);
Console.WriteLine();
}```

Output:

9999 + 0055 = 10054

Like 0 People on 22 December 2018

Login via:   x 