How to add two numbers represented by linked list in C++

Hello Friends, Today we are going to learn how to add two numbers represented by linked list in C++. First, we will store the two numbers in the linked list and then we will see how to perform addition and then print the resultant linked list. There are so many different approaches for performing the addition of two linked lists. But I will tell you the best approach to do this problem.

Let’s take an example to understand the question clearly then we will move ahead.

Number 1 =   4 -> 5

Number 2 =   1 -> 4 -> 5

Answer should be : 1 -> 9 -> 0

Now, we will understand the code, and then we will see the algorithm.

C++ code for adding two numbers represented by a linked list

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct Node* addlists(struct Node* first, struct Node* second);
struct Node {
    int data;
    struct Node* next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};

struct Node* makelist(int size)
{
    int value;
    cin>> value;
    
    Node* head = new Node(value);
    Node* tail = head;
    
    for(int i=0; i<size-1; i++)
    {
        cin>> value;
        tail->next = new Node(value);
        tail = tail->next;
    }
    
    return head;
}

void printlist(Node* n)
{
    while(n)
    {
        cout<< n->data << " ";
        n = n->next;
    }
    cout<< endl;
}

int main()
{
        int n, m;
        
        cin>>n;        // size of first linked list
        Node* first = makelist(n);                  // suppose input is 4 -> 5
        
        cin>>m;       // size of second linked list
        Node* second = makelist(m);                 // suppose input is 1 -> 4 -> 5
        
        Node* resultant = addlists(first,second);
        printlist(resultant);
    
    return 0;
}

Node* reverseList(Node* head)
{
Node* current = head;
Node* prev = NULL;
Node* next = NULL;

while(current != NULL)
{
next = current -> next;
current -> next = prev;
prev = current;
current = next;
}
return prev;
}
struct Node* addlists(struct Node* first, struct Node* second)
{
    first = reverseList(first);
    second = reverseList(second);
    int carry = 0, sum = 0;

Node* start = NULL;
Node* end = NULL;

while(first != NULL || second != NULL)
{
int a = (first != NULL)?first -> data:0;
int b = (second != NULL)?second -> data:0;

sum = carry + (a + b);
carry = (sum >= 10)?1:0;
sum = sum % 10;

if(start == NULL)
{
start = new Node(sum);
end = start;
}
else
{
end -> next = new Node(sum);
end = end -> next;
}

if(first != NULL)
first = first -> next;

if(second != NULL)
second = second -> next;
}
if(carry > 0)
end -> next = new Node(carry);

start = reverseList(start);

return start;
}

Output : 1 9 0

Understanding the Algorithm

The algorithm is quite simple. First, reverse both the given linked list and start performing the addition. Normally while adding two numbers we start with the rightmost digit and coming to the left. Here also I am doing the same by reversing the linked list and start adding from the first node. Initially carry is 0, but after performing addition if we get any carry that will be stored in the carry variable. We are creating the new node after performing the addition of each digit.

You can see our next tutorial too.

• How to rotate linked list by k nodes in C++