Multiply Linked Lists

Easy
0/40
Average time to solve is 15m
profile
Contributed by
22 upvotes
Asked in companies
AmazonSamsungAccolite

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5 6 3 -1
8 4 2 -1
Sample Output 1:
4 7 4 0 4 6 -1
Explanation of Sample Input 1:
563 * 842 = 474046
Sample Input 2:
2
7 5 9 4 6 -1
0 -1
0 2 3 4 0 - 1
0 0 1 -1
Sample Output 2:
0 -1
2 3 4 0 -1
Explanation of Sample Input 2:
75946 * 0 = 0
02340 * 001 = 2340
Hint

Multiply the linked list just like you multiply two numbers.

Approaches (1)
Pen-paper approach

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 : 

  1. Reverse both the linked lists and get their lengths.
  2. 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).
  3. Reverse the result list and remove leading zeros and return its head.
Time Complexity

O(N*M), where ‘N’ and ‘M’ are the number of nodes in the linked lists first and second respectively.

 

Each element of the first linked list is visited for all the nodes of the second linked list. So, the time complexity will be O(N*M).

Space Complexity

O(N+M), where ‘N’ and ‘M’ are the number of nodes in the linked lists first and second respectively.

 

As the new linked list is created for storing the multiplication of the two linked lists, whose maximum size can be the sum of the sizes of the two individual linked lists. Thus, the space complexity will be O(N+M).

Code Solution
(100% EXP penalty)
Multiply Linked Lists
Full screen
Console