Addition of Two Numbers Stored in a Linked List in reverse order

We are given two numbers stored in a Linked List in reverse order, where each node of the Linked List represents the digit in the given numbers such that value stored at the first node is the first digit of the number, we have to add the number and store the result again a Linked List in the reverse order

Ex:  6 -->5 -->4 -->3    => 3456 is the first number
     9 -->8 -->7  => 789 is the second number
     result => 5 -->4 -->2 -->4    (3456 + 987 = 4245)

Read more about Linked List here…

Algorithm

1. First, we will convert the linked list into the original number. (Note: digits are stored in reverse order of the original number)
2. Then, we will Sum both the numbers
3. Finally, we will store the resulting sum digit again into the linked list format in reverse order.

int convert_list_to_num(Node* list){
    int num=0, i=0;
    
    while(list != NULL){
        num = num + (pow(10,i)*(list->digit));
        list = list->next;
        i++;
    }
    return num;
}

Node* convert_sum_to_list(int sum){
    Node *head,*prev;

    while(num){
        Node *temp = new Node();
        temp->digit = num%10;
        num = num/10;
        temp->next = NULL;
        if(prev == NULL){  
            prev = temp;
            head = prev;
        }
        else{
            prev->next = temp;
            prev = prev->next;
       }
    return head;
}

Node* find_sum(Node *list1, Node *list2){
    int sum = 0;
    sum = convert_list_to_num(list1) + convert_list_to_num(list2);
    Node *list3 = convert_sum_to_list(sum);
    return list3;
}

CPP implementation of the above algorithm

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

class Node{
    public:
	    int digit;
	    Node *next;
};

int convert_list_to_num(Node* list){
    int num=0, i=0;
    
    while(list != NULL){
        num = num + (pow(10,i)*(list->digit));
        list = list->next;
        i++;
    }
    return num;
}

Node* convert_sum_to_list(int sum){
    Node *head=NULL,*prev=NULL;

    while(sum){
        Node *temp = new Node();
        temp->digit = sum%10;
        sum = sum/10;
        temp->next = NULL;
        if(prev == NULL){  
            prev = temp;
            head = prev;
        }
        else{
            prev->next = temp;
            prev = prev->next;
       }
   }
   return head;
}

Node* find_sum(Node *list1, Node *list2){
    int sum = 0;
    sum = convert_list_to_num(list1) + convert_list_to_num(list2);
    Node *list3 = NULL; 
    list3 =convert_sum_to_list(sum);
    return list3;
}

int main(){

	Node *list1=NULL, *list2=NULL, *current=NULL;

	//creating list1
	for(int i=6;i>=3;i--){
		Node *temp = new Node;
		temp->digit = i;
		temp->next = NULL;
		if(list1==NULL){
			current = temp;
			list1 = current;
	    }
	    else{
	    	current->next = temp;
		    current = current->next;
	    }
	}
	
	//printing list1
	cout<<"List1: ";
	current = list1;
	while(current!=NULL){
		cout<<current->digit<<"->";
		current = current->next;
	}
	cout<<"NULL"<<endl;
	

	//creating list2
	current = NULL;
	for(int i=9;i>=7;i--){
		Node *temp = new Node;
		temp->digit = i;
		temp->next = NULL;
		if(list2==NULL){
			current = temp;
			list2 = current;
	    }
	    else{
	    	current->next = temp;
		    current = current->next;
	    }
	}
	
	//priting list 2
	cout<<"List2: ";
	current = list2;
	while(current!=NULL){
		cout<<current->digit<<"->";
		current = current->next;
	}
	cout<<"NULL"<<endl;

	Node *list3 =find_sum(list1, list2);

	//printing list3
	cout<<"list3: ";
	while(list3!=NULL){
		cout<<list3->digit<<"->";
		list3 = list3->next;
	}
	cout<<"NULL"<<endl;

	return 0;
}

Output
List1: 6->5->4->3->NULL
List2: 9->8->7->NULL
list3: 5->4->2->4->NULL

The time complexity of the above algorithm in O(A+B), where A is the size of the first list, and B is the size of the second list.