Given a linked list of N nodes where each node represents digits of a number and a single-digit number M, the task is to multiply the list by M in-place and print the resulting linked list.
Examples:
Input: Linked list: 1 ? 2 ? 7 ? 3 ? NULL, M = 3
Output: 3 ? 8 ? 1 ? 9 ? NULL
Explanation: The given linked list represents the number 1273. Multiplying 1273 with 3 = 1273*3 = 3819. Hence, the resulting linked list is
3 ? 8 ? 1 ? 9 ? NULLInput: Linked list: 9 ? 9 ? 9 ? NULL, M = 2
Output: 1 ? 9 ? 9 ? 8 ? NULL
Explanation: The given linked list represents the number 999. Multiplying 999 with 2 = 999*2 = 1998. Hence, the resulting linked list is
1 ? 9 ? 9 ? 8 ? NULL
Approach: Since we are allowed to reverse the LL and add at most 1 extra node to it, the idea to solve this problem is to first reverse the linked list. Then, traverse the linked list and start multiplying M with every node adding the carry generated and updating the carry after each multiplication step. Again, reverse the modified linked list and print the resulting list.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Node of a Linked Listclass Node {public: int data; Node* next;};// Function to create a new// node with given dataNode* newNode(int data){ // Initialize new node Node* new_node = new Node; // Set the data field of the node new_node->data = data; new_node->next = NULL; // Return the new node return new_node;}// Function to reverse the linked listNode* reverse(Node* head){ Node* prev = NULL; Node* current = head; Node* next; // Traverse until curr!=null while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } // Return the head of the // reversed linked list return prev;}// Utility function to multiply a single digit// to a linked listNode* multiplyHelp(Node* head, int M){ // Store the head of list Node* res = head; // Stores the address of previous node Node* prev = NULL; // Initially set carry as 0 and product as 1 int carry = 0, product = 1; while (head != NULL) { // Multiply M with each digit product = head->data * M; // Add carry to product if carry exist product += carry; // Update carry for next calculation carry = product / 10; // Update the value of each nodes head->data = product % 10; // Move head and temp pointers to next nodes prev = head; head = head->next; } // If some carry is still there, // add a new node to list if (carry > 0) prev->next = newNode(carry); // Return head of the resultant list return res;}// Function to multiply a single digit// to a linked listNode* multiply(Node* head, int M){ // Reverse linked list head = reverse(head); // Multiply M from left to right of reversed list head = multiplyHelp(head, M); // Reverse the modified list and return its head return reverse(head);}// Function to print the linked listvoid printList(Node* node){ while (node != NULL) { cout << node->data; node = node->next; }}// Driver Codeint main(){ // Given Input list: 1->2->7->3 Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(7); head->next->next->next = newNode(3); int M = 3; // Function Call head = multiply(head, M); // Print resultant list printList(head); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Node of a Linked List static class Node { int data; Node next; }; // Function to create a new // node with given data static Node newNode(int data) { // Initialize new node Node new_node = new Node(); // Set the data field of the node new_node.data = data; new_node.next = null; // Return the new node return new_node; } // Function to reverse the linked list static Node reverse(Node head) { Node prev = null; Node current = head; Node next; // Traverse until curr!=null while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } // Return the head of the // reversed linked list return prev; } // Utility function to multiply a single digit // to a linked list static Node multiplyHelp(Node head, int M) { // Store the head of list Node res = head; // Stores the address of previous node Node prev = null; // Initially set carry as 0 and product as 1 int carry = 0, product = 1; while (head != null) { // Multiply M with each digit product = head.data * M; // Add carry to product if carry exist product += carry; // Update carry for next calculation carry = product / 10; // Update the value of each nodes head.data = product % 10; // Move head and temp pointers to next nodes prev = head; head = head.next; } // If some carry is still there, // add a new node to list if (carry > 0) prev.next = newNode(carry); // Return head of the resultant list return res; } // Function to multiply a single digit // to a linked list static Node multiply(Node head, int M) { // Reverse linked list head = reverse(head); // Multiply M from left to right of reversed list head = multiplyHelp(head, M); // Reverse the modified list and return its head return reverse(head); } // Function to print the linked list static void printList(Node node) { while (node != null) { System.out.print(node.data); node = node.next; } } // Driver Code public static void main(String[] args) { // Given Input list: 1.2.7.3 Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(7); head.next.next.next = newNode(3); int M = 3; // Function Call head = multiply(head, M); // Print resultant list printList(head); }}// This code contributed by gauravrajput1 |
Python3
# Python program for the above approach# Node of a Linked Listclass Node: def __init__(self, data): self.data = data; self.next = None; # Function to create a new# Node with given datadef newNode(data): # Initialize new Node new_Node = Node(data); # Return the new Node return new_Node;# Function to reverse the linked listdef reverse(head): prev = None; current = head; next = None; # Traverse until curr!=None while (current != None): next = current.next; current.next = prev; prev = current; current = next; # Return the head of the # reversed linked list return prev;# Utility function to multiply a single digit# to a linked listdef multiplyHelp(head, M): # Store the head of list res = head; # Stores the address of previous Node prev = None; # Initially set carry as 0 and product as 1 carry = 0; product = 1; while (head != None): # Multiply M with each digit product = head.data * M; # Add carry to product if carry exist product += carry; # Update carry for next calculation carry = product // 10; # Update the value of each Nodes head.data = product % 10; # Move head and temp pointers to next Nodes prev = head; head = head.next; # If some carry is still there, # add a new Node to list if (carry > 0): prev.next = newNode(carry); # Return head of the resultant list return res;# Function to multiply a single digit# to a linked listdef multiply(head, M): # Reverse linked list head = reverse(head); # Multiply M from left to right of reversed list head = multiplyHelp(head, M); # Reverse the modified list and return its head return reverse(head);# Function to print linked listdef printList(node): while (node != None): print(node.data,end=""); node = node.next; # Driver Codeif __name__ == '__main__': # Given Input list: 1.2.7.3 head = newNode(1); head.next = newNode(2); head.next.next = newNode(7); head.next.next.next = newNode(3); M = 3; # Function Call head = multiply(head, M); # Print resultant list printList(head);# This code is contributed by gauravrajput1 |
C#
// C# program for the above approachusing System;public class GFG { // Node of a Linked List class Node { public int data; public Node next; }; // Function to create a new // node with given data static Node newNode(int data) { // Initialize new node Node new_node = new Node(); // Set the data field of the node new_node.data = data; new_node.next = null; // Return the new node return new_node; } // Function to reverse the linked list static Node reverse(Node head) { Node prev = null; Node current = head; Node next; // Traverse until curr!=null while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } // Return the head of the // reversed linked list return prev; } // Utility function to multiply a single digit // to a linked list static Node multiplyHelp(Node head, int M) { // Store the head of list Node res = head; // Stores the address of previous node Node prev = null; // Initially set carry as 0 and product as 1 int carry = 0, product = 1; while (head != null) { // Multiply M with each digit product = head.data * M; // Add carry to product if carry exist product += carry; // Update carry for next calculation carry = product / 10; // Update the value of each nodes head.data = product % 10; // Move head and temp pointers to next nodes prev = head; head = head.next; } // If some carry is still there, // add a new node to list if (carry > 0) prev.next = newNode(carry); // Return head of the resultant list return res; } // Function to multiply a single digit // to a linked list static Node multiply(Node head, int M) { // Reverse linked list head = reverse(head); // Multiply M from left to right of reversed list head = multiplyHelp(head, M); // Reverse the modified list and return its head return reverse(head); } // Function to print the linked list static void printList(Node node) { while (node != null) { Console.Write(node.data); node = node.next; } } // Driver Code public static void Main(String[] args) { // Given Input list: 1.2.7.3 Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(7); head.next.next.next = newNode(3); int M = 3; // Function Call head = multiply(head, M); // Print resultant list printList(head); }}// This code contributed by Princi Singh |
Javascript
<script>// javascript program for the above approach // Node of a Linked Listclass Node { constructor() { this.data = 0; this.next = null; }} // Function to create a new // node with given data function newNode(data) { // Initialize new node var new_node = new Node(); // Set the data field of the node new_node.data = data; new_node.next = null; // Return the new node return new_node; } // Function to reverse the linked list function reverse(head) { var prev = null; var current = head; var next; // Traverse until curr!=null while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } // Return the head of the // reversed linked list return prev; } // Utility function to multiply a single digit // to a linked list function multiplyHelp(head , M) { // Store the head of list var res = head; // Stores the address of previous node var prev = null; // Initially set carry as 0 and product as 1 var carry = 0, product = 1; while (head != null) { // Multiply M with each digit product = head.data * M; // Add carry to product if carry exist product += carry; // Update carry for next calculation carry = parseInt(product / 10); // Update the value of each nodes head.data = product % 10; // Move head and temp pointers to next nodes prev = head; head = head.next; } // If some carry is still there, // add a new node to list if (carry > 0) prev.next = newNode(carry); // Return head of the resultant list return res; } // Function to multiply a single digit // to a linked list function multiply(head , M) { // Reverse linked list head = reverse(head); // Multiply M from left to right of reversed list head = multiplyHelp(head, M); // Reverse the modified list and return its head return reverse(head); } // Function to print the linked list function printList(node) { while (node != null) { document.write(node.data); node = node.next; } } // Driver Code // Given Input list: 1.2.7.3 var head = newNode(1); head.next = newNode(2); head.next.next = newNode(7); head.next.next.next = newNode(3); var M = 3; // Function Call head = multiply(head, M); // Print resultant list printList(head);// This code is contributed by gauravrajput1</script> |
Output
3819
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
