Linked List: Multiply two numbers represented by Linked Lists

Problem Statement:

You are given 2 LL, you need to get the multiplication of the 2 LL.

Example

Input: 1 -> 2
       2

Output: 24

Solution

We follow bellow steps for the solution:

1. Initialize a variable

2. Start traversing the LL

3. Add the first value to the variable.

4. From the next node, multiply the variable by 10 and then add the value

5. Repeat the above step till the end of the list.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <stack> 

using namespace std;

struct Node 
{
    int data;
    struct Node* next;
};

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

long multiply_two_lists (struct Node* first, struct Node* second) 
{ 
    int num1 = 0, num2 = 0; 
      
    while (first || second) 
    { 
        if (first) 
        { 
            num1 = num1*10 + first->data; 
            first = first->next; 
        } 
        if (second) 
        { 
            num2 = num2*10 + second->data; 
            second = second->next; 
        } 
    } 
  
    return num1*num2; 
} 

   int main()
{
    struct Node *list_1 = NULL; 
    struct Node *list_2 = NULL; 

    insert_at_begenning(&list_1,1);
    insert_at_begenning(&list_1,2);

    insert_at_begenning(&list_2,2);

    long result = multiply_two_lists (list_1, list_2);
 
    printf("\n The result is = %ld\n", result);

    return 0;
}

Output:

The result is = 42