Multiply two numbers represented by Linked Lists

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Proper understanding of concepts based on Linked Lists can give you an edge in a coding interview.

Problem Statement

In this problem, we are given two linked lists, L1 and L2. Both L1 and L2 are numbers represented as linked lists. We are required to multiply these Lists and produce the output.

Problem Statement Understanding

Let’s try to understand the problem with help of examples by referring the best online learning sites for programming.

Suppose the given linked lists are:

Now, according to the problem statement, these linked lists L1 and L2 are actually two numbers which are represented using linked lists.
For example, we can represent

• The number 23 as 2→3 using linked list.
• The number 234 as 2→3→4 using linked list.
• More generically speaking, we can represent a number abcd as a→b→c→d using linked list.

And our output is the multiplication of these two numbers L1 and L2, represented as a linked list.

• As L1 = 5→6→1, so the number is 561.
• And as L2 = 4→2, the number is 42.

Output = 561*42 = 23562

Let’s say if:

• Corresponding numbers for L1 and L2 will be 2345 and 345.

Output = 2345*345 = 809025

Some more examples:

Input: L1 = 3→2→1, L2 = 2→1
Output: 6741

Input: L1 = 3→2, L2 = 1→7
Output: 544

Input: L1 = 9→8→7, L2 = 1→2→3
Output: 121401

Now, I hope that from the above examples, you got the idea about what the problem is. So now let’s move towards finding some approach to solve this problem.

Approach

Firstly, traverse through both the lists and produce the numbers required to be multiplied, and then return the multiplied values of the two numbers.

Algorithm for producing the number from linked list representation:

• Initialize a variable num to zero.
• Begin traversing through the linked list.
• Add the data of the first node to this variable num.
• Second node onwards,
  1) multiply the variable num by 10
  2) and take the modulus of this value by 10⁹+7 as well,
  3) and then add the data of the node to the variable num.
• Repeat the previous step until we arrive at the last node of the list.

First, using the above-discussed algorithm for producing the number from linked list representation, we will produce the required numbers from the given linked lists L1 and L2.

After the numbers have been produced, we will multiply them to get the output.

Dry Run

Code Implementation

#include
#include
using namespace std;

// Linked list node
struct Node
{
    int val;
    struct Node* next;
};

// Function for creating a new node with given value
struct Node *create_node(int val)
{
    struct Node *node_new = (struct Node *)
malloc(sizeof(struct Node));

// putting the data into the new node.
    node_new->val = val;
    // initially new node points to NULL
    node_new->next = NULL;

    return node_new;
}

// Function for inserting a node
// at the start of the Linked List
void push(struct Node** head_ref, int new_val)
{
    // assigning the node
    struct Node* node_new = create_node(new_val);

    // Now, link old list off the new node
    node_new->next = (*head_ref);

    // moving the head inorder to point to the new node
    (*head_ref) = node_new;
}

// to multiply data present in the two linked lists
long long multiplication (Node* list_one, Node* list_two)
{
    long long n= 1000000007;
    long long first_num = 0, second_num = 0;
    while (list_one || list_two){
        
        if(list_one){
            first_num = ((first_num)*10)%n + list_one->val;
            list_one = list_one->next;
        }
        
        if(list_two)
        {
            second_num = ((second_num)*10)%n + list_two->val;
            list_two = list_two->next;
        }
        
    }
    return ((first_num%n)*(second_num%n))%n;
}

// For printing the linked list
void display_list(struct Node *node)
{
    while(node != NULL)
    {
        cout<val;
        if(node->next)
            cout<<"->";
        node = node->next;
    }
}

// Driver function
int main()
{
    struct Node* one = NULL;
    struct Node* two = NULL;

    // creating list one 5->6->1
    push(&one, 1);
    push(&one, 6);
    push(&one, 5);
    printf("List one is: ");
    display_list(one);
    
    cout<<”\n”;

    // creating list two 4->2
    push(&two, 2);
    push(&two, 4);
    printf("List two is: ");
    display_list(two);
    
    cout<<”\n”;

    // Results after multiplying the two numbers.
    cout<<”Answer: “<

						 

Output

List one is: 5→6→1
List two is: 4→2

Answer:>Answer: 23562

Time Complexity: O(N+M), where N and M are lengths of the input linked lists.

In this article, we have tried to explain the algorithm for multiplying two numbers represented as Linked Lists. This problem is interesting as well as important from the interview’s point of view. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.