Last Updated: 22 Dec, 2020
Multiply Linked Lists
Easy
Asked in companies
Given two numbers represented by linked lists. Your task is to find the multiplied list and return the head of the multiplied list.
The multiplied list is a linked list representation of the multiplication of two numbers.
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains the elements of the first singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
The second line of each test case contains the elements of the second singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format:
For each test case, print the multiplied linked list. The elements of the multiplied list should be single-space separated, terminated by -1.
The output of each test case is printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N, M <= 100
0 <= data <= 9
Where N and M are the number of nodes in the two linked lists.
Time Limit: 1 sec
Approaches
The idea is to use the simple method of multiplying two numbers. We multiply two numbers starting from their least significant digit and moving towards the most significant digit. So we need to access the nodes of linked lists from last to first. First step would be to reverse both the linked lists. Then multiply both the linked lists starting from their heads and then reverse the resulting multiplied list and return its head.
Algorithm :
- Reverse both the linked lists and get their lengths.
- Make a list, result, of size equal to the sum of the sizes of both the input linked lists that is M+N (as this can be the maximum size of the multiplied list). Initially, all nodes of the list result have value 0. Now, for every node of the second linked list, multiply its value with every node of the first linked list (like normal multiplication) and store the value of multiplication of every two nodes in their respective position in the result list.
Now the resulting node (after multiplication of two nodes) can be greater than 9 thus keep the carry for the next node.
Now for the next node of the second linked list, store the values of multiplication from the next node of the previous start node in the result list (like leaving the last column in normal multiplication). - Reverse the result list and remove leading zeros and return its head.