Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
Do linked lists have fixed sizes?
3.2.
What are the limitations of linked lists?
3.3.
How many types of linked lists are there?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Multiply two numbers represented by Linked Lists

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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

  1. Firstly, we initialise two variables with value zero to store the value of the two linked lists.
  2. We iterate over the two lists, multiplying their values by ten and adding them to get the value.
  3. We multiply the two numbers and store the result in a new list.
  4. 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;
}
You can also try this code with Online C++ Compiler
Run Code


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

Frequently Asked Questions

Do linked lists have fixed sizes?

The size of linked lists is dynamic; they expand and contract as nodes are added and withdrawn, and they do not require more memory than the number of objects in the collection.

What are the limitations of linked lists?

The linked list uses up more memory to store the elements than an array because each node of the linked list points to a pointer, which takes up more memory. Traversing the nodes of a linked list is quite difficult. We won't be able to access any node at random in this case.

How many types of linked lists are there?

There are four main types of linked lists: singly-linked lists, doubly linked lists, circular linked lists and circular doubly-linked lists.

Conclusion

In conclusion, we discussed how to multiply two numbers represented by linked lists. Then, we discussed the algorithm and complexity of the approach.
Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.
Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass