Home » Interview coding problems/challenges

Sum of two numbers represented by linked lists

Solution of the sum of two numbers represented by linked lists – this problem has been featured in the interview round of many big tech companies such as Amazon, Accolite, MakeMyTrip, Morgan Stanley, Snapdeal, Qualcomm, Flipkart, etc. Submitted by Divyansh Jaipuriyar, on April 30, 2020

Problem statement

Given two numbers represented by two linked lists of size N1 and N2. The task is to return a sum list. The sum list, which is a linked list representation of the addition of two input numbers.

Input

The first line of input contains the number of test cases T. For each test case, the first line of input contains the length of the first linked list and the next line contains N1 elements of the linked list. Again, the next line contains N2, and the following line contains M elements of the linked list.

Output

Output the resultant linked list representing the sum of given two linked list.

Explanation with example

    Input: 
    T  = 1
    N1 = 3
    [1->5->4]
    N2 = 3
    [2->3->5]

    Output: 
    [3->8->9], as 451+532 = 983

    Input: 
    T  = 1
    N1 = 3
    [2->4->3]
    N2 = 3
    [5->6->4]
    Output: 
    [7->0->8], as 342+465 = 807   

Solution Approach

We will use the same way of addition as we use to do during elementary school, we will keep track of carry using a variable car and traverse digit by digit sum starting from the head of two linked list which contains least significant digit to most significant digits.

Pseudo Code

Node sum(Node a,Node b){
	//Let Temp1 and temp2 be some Nodes
	int carry=0    // initilise carry as 0
	// temp2 is used as dummy for adding new node and 
	// temp1 will be use as the header for the 
	// sum value linked list
	temp2=temp1    
	int x,y        //used for storing nodes values
	while(a!=NULL or b!=NULL)
	{
		if(a!=NULL)
		{x=a->data,a=a->next;}
		else
		x=0
		if(b!=NULL)
		{y=b->data,b=b->next;}
		else
		y=0
		int sum=x+y+carry
		temp2->next=new Node(sum%10)   // store the digit(0-9)
		carry=sum/10                   // sum/10 gives carry
		temp2=temp2->next
	}
	if(carry!=0)      // if carry is not zero then add it at last.
		temp2->next=new Node(carry)
	return temp1->next // return the new Node head
}

Time complexity for above process is O(max(len(N1,N2))

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Node //declare Node
    {
    Node* next;
    int data;
    Node(int data)
    {
        this->data = data; // node value
        this->next = NULL; // node pointer
    }
};

Node* addNode(Node* head, int value)
{
    // declare two nodes temp and p
    Node *temp, *p;
    // createNode will return a new node with
    // data = value and next pointing to NULL.
    temp = new Node(value);
    if (head == NULL) {
        head = temp; // when linked list is empty
    }
    else {
        p = head; // assign head to p
        while (p->next != NULL) {
            // traverse the list until p is the last node.
            // The last node always points to NULL.
            p = p->next;
        }
        // Point the previous last node to the
        // new node created.
        p->next = temp;
    }
    return head;
}

Node* sum(Node* a, Node* b)
{
    Node *temp1, *temp2; // initilise two Nodes
    temp1 = new Node(0);
    temp2 = temp1;
    int x, y;
    int carry = 0; // initially carry is zero
    while (a != NULL or b != NULL) {
        // if node a is NOT NULL then x=a->data
        if (a != NULL) {
            x = a->data;
            a = a->next;
        }
        else
            x = 0;
        if (b != NULL) {
            // if node a is NOT NULL then x=a->data
            y = b->data;
            b = b->next;
        }
        else
            y = 0;
        int sum1 = x + y + carry;
        temp2->next = new Node(sum1 % 10);
        carry = sum1 / 10;
        temp2 = temp2->next;
    }
    if (carry) // if carry is not zero
        temp2->next = new Node(carry);
    // return head pointer of the linked
    // list after summation.
    return temp1->next;
}

// function to print linked list
void print(Node* head)
{
    while (head != NULL) {
        if (head->next != NULL)
            cout << head->data << "->";
        else
            cout << head->data;
        head = head->next;
    }
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of node N1: ";
        ll n1, n2;
        cin >> n1;

        Node *a, *b;
        ll x;

        cout << "Enter its elements: ";
        for (ll i = 0; i < n1; i++) {
            cin >> x;
            if (i == 0) {
                a = new Node(x);
            }
            else
                a = addNode(a, x);
        }

        cout << "Enter size of node N2: ";
        cin >> n2;

        cout << "Enter its elements: ";
        for (ll i = 0; i < n2; i++) {
            cin >> x;
            if (i == 0) {
                b = new Node(x);
            }
            else
                b = addNode(b, x);
        }

        cout << "The final sum is: ";
        print(sum(a, b));
        cout << "\n";
    }
    return 0;
}

Output

Enter number of test cases: 3
Enter size of node N1: 3
Enter its elements: 2 3 4
Enter size of node N2: 3
Enter its elements: 8 1 7
The final sum is: 0->5->1->1
Enter size of node N1: 3
Enter its elements: 2 1 3
Enter size of node N2: 4
Enter its elements: 1 2 3 4
The final sum is: 3->3->6->4
Enter size of node N1: 2
Enter its elements: 1 2
Enter size of node N2: 2
Enter its elements: 2 4
The final sum is: 3->6