Introduction
A linked list is a linear data structure in which the entries are not kept in memory in the same sequence. A pointer connects each link element to the one succeeding it. The structure looks similar to this:
Let’s discuss how we solve this in C++.
Problem Statement
In this problem, we are given two numbers represented by linked lists. We have to multiply the numbers and display the result.
Sample Examples
Example 1:
Input :
Linked List 1: 7 -> 4 -> 9
Linked List 2: 8 -> 3
Output : 62167
Explanation : The product of 749 and 83 is 62167
Example 2:
Input :
Linked List 1: 4 -> 9 -> 5
Linked List 2: 6 -> 1
Output : 30195
Explanation : The product of 495 and 61 is 30195.
Approach
In this approach, we traverse both lists and get the numbers we have to multiply. Then after multiplying them, we return the solution as a list.
Also read - Merge sort in linked list
Steps of Algorithm
- Firstly, we initialise two variables with value zero to store the value of the two linked lists.
- We iterate over the two lists, multiplying their values by ten and adding them to get the value.
- We multiply the two numbers and store the result in a new list.
- This new list is displayed as the answer.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addNewNode(struct Node** head, int new_val) {
struct Node* newNode = new Node;
newNode->data = new_val;
newNode->next = *head;
*head = newNode;
}
void multiplyLL(struct Node* firstList, struct Node* secList,
struct Node** resultList) {
int no1 = 0, no2 = 0;
while (firstList || secList) {
if (firstList) {
no1 = no1 * 10 + firstList->data;
firstList = firstList->next;
}
if (secList) {
no2 = no2 * 10 + secList->data;
secList = secList->next;
}
}
int result = no1 * no2;
while (result) {
addNewNode(resultList, result % 10);
result /= 10;
}
}
void dispList(struct Node *node) {
while(node != NULL) {
cout<<node->data;
if(node->next)
cout<<"->";
node = node->next;
}
cout << "\n";
}
int main(void) {
struct Node* firstList = NULL;
struct Node* secList = NULL;
addNewNode(&firstList, 5);
addNewNode(&firstList, 9);
addNewNode(&firstList, 4);
dispList(firstList);
addNewNode(&secList, 1);
addNewNode(&secList, 6);
dispList(secList);
struct Node* resultList = NULL;
multiplyLL(firstList, secList, &resultList);
dispList(resultList);
return 0;
}
Output:
4->9->5
6->1
3->0->1->9->5
Complexity Analysis
Time Complexity: O(N+M), where N and M are the sizes of the two given linked lists.
Explanation: In this approach, the two linked lists determine the time complexity of the program.
Space Complexity: O(M+N)
Explanation: In this approach, the space required depends on the sizes of the two given linked lists.
Also see, Rabin Karp Algorithm