Multiply two numbers represented by Linked Lists

In this article, we will learn how to multiply two numbers represented by linked lists. We need to multiply two numbers formed by the linked list.

Problem Statement

In this problem, we are given two linked lists, L1 and L2. Both L1 and L2 are numbers represented as linked lists. We are required to multiply these Lists and produce the output.

Problem Statement Understanding how to multiply two linked lists

Let’s try to understand the problem with help of examples by referring the best online learning sites for programming.

Suppose the given linked lists are:

Now, according to the problem statement, these linked lists L1 and L2 are actually two numbers which are represented using linked lists.
For example, we can represent

  • The number 23 as 2→3 using linked list.
  • The number 234 as 2→3→4 using linked list.
  • More generically speaking, we can represent a number abcd as a→b→c→d using linked list.

And our output is the multiplication of these two numbers L1 and L2, represented as a linked list.

  • As L1 = 5→6→1, so the number is 561.
  • And as L2 = 4→2, the number is 42.

Output = 561*42 = 23562

Let’s say if:

  • Corresponding numbers for L1 and L2 will be 2345 and 345.

Output = 2345*345 = 809025

Some more examples:

Input: L1 = 3→2→1, L2 = 2→1
Output: 6741

Input: L1 = 3→2, L2 = 1→7
Output: 544

Input: L1 = 9→8→7, L2 = 1→2→3
Output: 121401

Now, I hope that from the above examples, you got an idea about what the problem is. So now let’s move towards finding some approach to solve this problem.

Approach to multiply two numbers represented by linked lists.

Firstly, traverse through both lists and produce the numbers required to be multiplied, and then return the multiplied values of the two numbers.

Algorithm to multiply two numbers represented by linked lists
  • Initialize a variable num to zero.
  • Begin traversing through the linked list.
  • Add the data of the first node to this variable num.
  • Second node onwards,
    1) multiply the variable num by 10
    2) and take the modulus of this value by 109+7 as well,
    3) and then add the data of the node to the variable num.
  • Repeat the previous step until we arrive at the last node of the list.

First, using the above-discussed algorithm for producing the number from linked list representation, we will produce the required numbers from the given linked lists L1 and L2.

After the numbers have been produced, we will multiply them to get the output.

Dry Run of multiply two numbers represented by linked lists


Code Implementation

#include
#include

struct Node
{
    int data;
    struct Node* next;
};
   
// Function to create a new node
// with given data
struct Node *newNode(int data)
{
    struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
   
// Function to insert a node at the
// beginning of the Linked List
void push(struct Node** head_ref, int new_data)
{
    // allocate node
    struct Node* new_node = newNode(new_data);
   
    // link the old list off the new node
    new_node->next = (*head_ref);
   
    // move the head to point to the new node
    (*head_ref) = new_node;
}
   
// Multiply contents of two linked lists
long long multiplyTwoLists (struct Node* first,struct Node* second)
{
    long long N= 1000000007;
    long long num1 = 0, num2 = 0;
    while (first || second){
         
        if(first){
            num1 = ((num1)*10)%N + first->data;
            first = first->next;
        }
         
        if(second)
        {
            num2 = ((num2)*10)%N + second->data;
            second = second->next;
        }
         
    }
    return ((num1%N)*(num2%N))%N;
}
   
// A utility function to print a linked list
void printList(struct Node *node)
{
    while(node != NULL)
    {
        printf("%d",node->data);
        if(node->next)
            printf("->");
        node = node->next;
    }
    printf("\n");
}
   
// Driver program to test above function
int main()
{
    struct Node* first = NULL;
    struct Node* second = NULL;
   
    // create first list 9->4->6
    push(&first, 6);
    push(&first, 4);
    push(&first, 9);
    printf("First List is: ");
    printList(first);
   
    // create second list 8->4
    push(&second, 4);
    push(&second, 8);
    printf("Second List is: ");
    printList(second);
   
    // Multiply the two lists and see result
    printf("Result is: ");
    long long ans = multiplyTwoLists(first, second);
    printf("%lld",ans);
   
    return 0;
}
#include
#include
using namespace std;

// Linked list node
struct Node
{
    int val;
    struct Node* next;
};

// Function for creating a new node with given value
struct Node *create_node(int val)
{
    struct Node *node_new = (struct Node *)
malloc(sizeof(struct Node));

// putting the data into the new node.
    node_new->val = val;
    // initially new node points to NULL
    node_new->next = NULL;

    return node_new;
}

// Function for inserting a node
// at the start of the Linked List
void push(struct Node** head_ref, int new_val)
{
    // assigning the node
    struct Node* node_new = create_node(new_val);

    // Now, link old list off the new node
    node_new->next = (*head_ref);

    // moving the head inorder to point to the new node
    (*head_ref) = node_new;
}

// to multiply data present in the two linked lists
long long multiplication (Node* list_one, Node* list_two)
{
    long long n= 1000000007;
    long long first_num = 0, second_num = 0;
    while (list_one || list_two){
        
        if(list_one){
            first_num = ((first_num)*10)%n + list_one->val;
            list_one = list_one->next;
        }
        
        if(list_two)
        {
            second_num = ((second_num)*10)%n + list_two->val;
            list_two = list_two->next;
        }
        
    }
    return ((first_num%n)*(second_num%n))%n;
}

// For printing the linked list
void display_list(struct Node *node)
{
    while(node != NULL)
    {
        cout<val;
        if(node->next)
            cout<<"->";
        node = node->next;
    }
}

// Driver function
int main()
{
    struct Node* one = NULL;
    struct Node* two = NULL;

    // creating list one 5->6->1
    push(&one, 1);
    push(&one, 6);
    push(&one, 5);
    printf("List one is: ");
    display_list(one);
    
    cout<<”\n”;

    // creating list two 4->2
    push(&two, 2);
    push(&two, 4);
    printf("List two is: ");
    display_list(two);
    
    cout<<”\n”;

    // Results after multiplying the two numbers.
    cout<<”Answer: “<

						 
class Multiply
{
    static class Node
    {
        int data;
        Node next;
        
        Node(int data){
            this.data = data;
            next = null;
        }
    }
    // Multiply contents of two linked lists
    static long multiplyTwoLists(Node first, Node second)
    {
        long N = 1000000007;
        long num1 = 0, num2 = 0;

        while (first != null || second != null){
            
            if(first != null){
                num1 = ((num1)*10)%N + first.data;
                first = first.next;
            }
            
            if(second != null)
            {
                num2 = ((num2)*10)%N + second.data;
                second = second.next;
            }
            
        }
        return ((num1%N)*(num2%N))%N;
    }
    static void printList(Node node)
    {
        while(node != null)
        {
            System.out.print(node.data);
            if(node.next != null)
                System.out.print("->");
            node = node.next;
        }
        System.out.println();
    }

    // Driver program to test above function
    public static void main(String args[])
    {
        // create first list 9->4->6
        Node first = new Node(9);
        first.next = new Node(4);
        first.next.next = new Node(6);
        System.out.print("First List is: ");
        printList(first);

        // create second list 8->4
        Node second = new Node(8);
        second.next = new Node(4);
        System.out.print("Second List is: ");
        printList(second);

        // Multiply the two lists and see result
        System.out.print("Result is: ");
        System.out.println(multiplyTwoLists(first, second));
    }
}

class Node:
    
    def __init__(self, data):
        
        self.data = data
        self.next = None
    
class LinkedList:

    def __init__(self):

        self.head = None

    # Function to insert a node at the
    # beginning of the Linked List
    def push(self, new_data):
    
        # Create a new Node
        new_node = Node(new_data)

        # Make next of the new Node as head
        new_node.next = self.head

        # Move the head to point to new Node
        self.head = new_node
        
    # Function to print the Linked List
    def printList(self):
        
        ptr = self.head

        while (ptr != None):
            print(ptr.data, end = '')
            if ptr.next != None:
                print('->', end = '')
                
            ptr = ptr.next
            
        print()

# Multiply contents of two Linked Lists
def multiplyTwoLists(first, second):

    num1 = 0
    num2 = 0

    first_ptr = first.head
    second_ptr = second.head
    
    while first_ptr != None or second_ptr != None:
        if first_ptr != None:
            num1 = (num1 * 10) + first_ptr.data
            first_ptr = first_ptr.next
    
        if second_ptr != None:
            num2 = (num2 * 10) + second_ptr.data
            second_ptr = second_ptr.next
    
    return num1 * num2

# Driver code
if __name__=='__main__':

    first = LinkedList()
    second = LinkedList()

    first.push(1)
    first.push(6)
    first.push(5)

    print("First list is: ", end = '')
    first.printList()

    second.push(2)
    second.push(4)

    print("Second List is: ", end = '')
    second.printList()

    result = multiplyTwoLists(first, second)
    print("Result is: ", result)

Output

List one is: 5→6→1
List two is: 4→2

Answer: 23562

Time Complexity to multiply two numbers represented by linked lists: O(N+M), where N and M are lengths of the input linked lists.

In this blog, we have tried to explain the algorithm and approach for multiply two numbers represented by Linked Lists. This problem is interesting as well as important from the interviewee’s point of view. Also, you can solve the problems regarding the Linked list, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. What are the 4 types of linked lists?
  2. Types of linked lists are:

    • Singly-linked list
    • Doubly linked list
    • Circular linked list
    • Circular doubly linked list
  3. How do you multiply two numbers using pseudocode?
  4. You can multiply two numbers as follows:

    • Take input as A and B.
    • Compute C = A*B.
    • If C is not equal to 0 then print C.
    • Else print 0.
    • Terminate the program
  5. Why do we use a linked list?
  6. Linked lists are used because of their efficient insertion and deletion operations.

  7. Where we can use a linked list?
  8. Linked lists are used in the implementation of stack and queue.
    Implementations of the graph.

Leave a Reply

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