Add two numbers represented by linked lists


Category: Data Structure And Algorithms Tags: C#, Interview Question

Two given numbers below represented by linked lists:

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

5 -> 5 (55)

Addition of these should be:

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


Like 0 People
Asked on 22 December 2018
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 127
Questions: 9
Given Best Solutions: 8 *

Answers:

Nikhil Joshi

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

To add prefix to the smaller linked list:

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

To print a linked list:

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

To add two lists:

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 len1 = GetLinkedListLength(number1);
    int len2 = GetLinkedListLength(number2);
    int difference = len1 - len2;
    //if number1 is bigger than number2 than prefix of 0 has to be added in number2
    //to make linked list equal
    //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)
        number2 = AddPrefix(number2, difference);
    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();
    Console.ReadLine();
}

Output:

9999 + 0055 = 10054

Like 0 People on 22 December 2018

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x