Multiply Linked Lists

Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

Problem Statement

We will be given two numbers in the form of a linked list, and we need to return a third list that will be the product of both the given lists.

Problem Statement Understanding

Let's try to understand the problem with the help of an example:

If the linked lists given to us be list1 = 2→3→5→NULL and list2 = 1→4→NULL.

  • In numeric form, list1 = 2→3→5→NULL can be represented as 235 and list2 = 1→4→NULL can be represented as 14.
  • So, according to the problem statement, we need to multiply the given linked lists, i.e., find the product of the numeric form of list1 and list2, and return the product in the form of a linked list.
  • The output list will be 3→2→9→0→NULL, because the product of the numeric form of list1 and list2 is *23514 = 3290**.

Let’s take another example. If the linked lists given to us be list1 = 6→7→4→NULL and list2 = 2→9→5→NULL.

  • In this case, the numeric form of list1 will be 674, and list2 will be 295. So, our output will be the linked list representation of *674295 = 198830, which will be 1→9→8→8→3→0→NULL**.
Some more examples

Sample Input 1:

  • list1: 1→3→5→NULL
  • list2: 2→3→4→NULL

Sample Output 1: 3→1→5→9→0→NULL

Sample Output 2:

  • list1: 1→6→4→8→NULL
  • list2: 1→2→3→4→NULL

Sample Output 2: 2→0→3→3→6→3→2→NULL

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach

  • The input list given to us will contain the most significant digit as the head and the least significant as the last node.
  • We know that, for multiplication, we need to start multiplying the digit from the least significant digit to the most significant one.
  • We cannot traverse backward in the list so, first, we need to reverse both the lists.
  • Now, we will multiply each digit of the second list one by one with a complete first list (just as we do a normal multiplication on pen-paper).
  • We will multiply the first digit of the second list with the complete first list and save it to use afterwards.
  • Then, we will multiply the second digit of the second list with the complete first list and add this list with the previously obtained list by shifting the elements of this list by one place to the right.
  • We will repeat the above steps of multiplication of digits of second list with the complete first list until we reach the second list's end.
  • Remember to take care of carry while doing addition and multiplication.
  • Finally, we will reverse the obtained list and return it.

Algorithm

  • Reverse both the linked lists.
  • Create a dummy node with a value of -1 and name it as ans. Also, initialize a pointer ans_itr with the address of the dummy node and a pointer l2_itr with the head of the second list.
  • Now, run a while loop till l2_itr is not NULL.
  • Create a head pointer that will call multiplyLinkedListWithDigit function with l1 and l2_itr->data as parameters. (This function will multiply the single digit of the second list’s node with the complete first list).
  • Now, control moves to multiplyLinkedListWithDigit function:
    • Create a dummy node with a value of -1 and name it head. Also, initialize a pointer named curr with it and an integer variable carry with zero.
    • Run a while loop till l1 is not NULL or carry is non-zero.
    • Calculate the sum variable as the sum of carry and If l1 is not NULL, then the product of digit and l1->data.
    • Now, update carry by removing the last digit from the sum by doing sum/10.
    • Update sum as the last digit of sum, i.e., sum %= 10.
    • Create a new node with the value of sum and attach it after the curr node.
    • If l1 is not NULL, advance l1 by a node
    • Advance curr pointer by one node.
    • After execution of the while loop, return head->next as the head was the dummy node created initially.
  • Now, advance the l2_itr to the next node for further multiplication.
  • Update the ans_itr function by calling the addTwoLinkedList function with ans_itr and head as parameters.
  • Now the control moves to addTwoLinkedList function:
    • Initialize a prev pointer with the head of the first list and an integer variable carry with zero.
    • Run a while loop till l2 is not NULL or carry is non-zero.
    • Calculate sum by adding carry, prev->next->data if prev->next is not NULL and l2->data if l2 is not NULL.
    • Now, update carry by removing the last digit from the sum by doing sum/10.
    • Update sum as the last digit of sum i.e., sum %= 10.
    • Check if prev->next is NULL or not.
    • If it is not NULL then, assign sum value to prev->next->data.
    • Else, create a new node with sum value and attach it after prev.
    • If l2 is not NULL, advance l2 by one node.
    • Advance prev by one node.
    • After execution of the loop, return l1.
  • Advance ans_itr by one node.
  • After completion of the while loop, advance ans by one node, as ans was a dummy node created initially.
  • Now, reverse the list having ans as head and return it.

Note: To understand the algorithm better, follow along with code.

Dry Run

Code Implementation

#include
using namespace std;
class Node {
    public:
    int data;
    Node* next;
    // constructor
    Node(int x){
        data = x;
        next = NULL;
    }
};
// This function prints the data of a given list 
void print(Node* head)
{
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout<<"NULL";
}
// This function will reverse a given list
Node* reverse(Node *head)
{
    Node *prev = NULL, *current = head, *next;
    while (current != NULL)
    {
        next  = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
// This function will add two lists and it also shifts the
// second list by one place while adding and then returns the
// result in a third list
Node* addTwoLinkedList(Node *l1, Node *l2) {
    Node *prev = l1;
    int carry = 0;
    while (l2 != NULL || carry != 0) {
        int sum = carry 
+ (prev->next != NULL ? prev->next->data : 0) 
+ (l2 != NULL ? l2->data : 0);

        carry = sum / 10;
        sum = sum % 10;

        if (prev->next != NULL)
            prev->next->data = sum;
        else
            prev->next = new Node(sum);

        if (l2 != NULL)
            l2 = l2->next;
        prev = prev->next;
    }
    return l1;
}

// This function multiplies a linked list with an integer and
// returns the result of multiplication as a list
Node* multiplyLinkedListWithDigit(Node* l1, int digit) {
    Node* head = new Node(-1); // dummy node
    Node* curr = head;

    int carry = 0;
    while (l1 != NULL || carry != 0) {
        int sum = carry + (l1 != NULL ? (l1->data * digit) : 0);

        carry = sum / 10;
        sum = sum % 10;

        curr->next = new Node(sum);

        if (l1 != NULL)
            l1 = l1->next;
        curr = curr->next;
    }

    return head->next;
}
// This function will multiply two linked lists and return
// a third list which will be having the result of 
// multiplication
Node* multiplyTwoLL(Node* l1, Node* l2) {
    l1 = reverse(l1);
    l2 = reverse(l2);

    Node* ans = new Node(-1); // dummy node
    Node* ans_itr = ans;
    Node* l2_itr = l2;

    while (l2_itr != NULL) {
        Node* head = multiplyLinkedListWithDigit(l1, l2_itr->data);
        l2_itr = l2_itr->next;
        ans_itr = addTwoLinkedList(ans_itr,head);
        ans_itr = ans_itr->next;
    }
    
    ans = ans->next;
    return reverse(ans);
}

int main(){
    Node *list1 = new Node(2);
    list1->next = new Node(3);
    list1->next->next = new Node(5);

    Node *list2 = new Node(1);
    list2->next = new Node(4);

    cout<<"Linked list obtained by multiplying list1 and list2: "<

						 

Output

Linked list obtained by multiplying list1 and list2:
3 -> 2 -> 9 -> 0 -> NULL

Time Complexity: O(N*M), where N and M are the numbers of nodes in the linked list 1 and 2.
Space Complexity: O(X), where X will be the number of nodes in the resultant list.

So, in this blog, we have tried to explain how you can multiply two linked lists in the most optimal way. This is one of the good problems that helps you strengthen your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).

Previous post Linked List Deleting Node
Next post Queue Linked List Implementation

Leave a Reply

Your email address will not be published. Required fields are marked *