Product of the nodes of a Singly Linked List
Given a singly linked list. The task is to find the product of all of the nodes of the given linked list.
Examples:
Input : List = 7->6->8->4->1
Output : Product = 1344
Product of nodes: 7 * 6 * 8 * 4 * 1 = 1344
Input : List = 1->7->3->9->11->5
Output : Product = 10395
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Algorithm:
- Initialize a pointer ptr with the head of the linked list and a product variable with 1.
- Start traversing the linked list using a loop until all the nodes get traversed.
- Multiply the value of the current node to the product i.e. product *= ptr -> data.
- Increment the pointer to the next node of linked list i.e. ptr = ptr ->next.
- Repeat the above two steps until end of linked list is reached.
- Finally, return the product.
Below is the implementation of above algorithm:
C++
// C++ implementation to find the product of // nodes of the Linked List #include <iostream> using namespace std; // A Linked list node struct Node { int data; struct Node* next; }; // 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 = new Node; /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // Function to find the product of // nodes of the given linked list int productOfNodes( struct Node* head) { // Pointer to traverse the list struct Node* ptr = head; int product = 1; // Variable to store product // Traverse the list and // calculate the product while (ptr != NULL) { product *= ptr->data; ptr = ptr->next; } // Return the product return product; } // Driver Code int main() { struct Node* head = NULL; // create linked list 7->6->8->4->1 push(&head, 7); push(&head, 6); push(&head, 8); push(&head, 4); push(&head, 1); cout << "Product = " << productOfNodes(head); return 0; } |
C
//C implementation to find the product of nodes of the linked list #include <stdio.h> #include <stdlib.h> //A linked list node struct Node{ int data; struct Node *next; }; //Creating node head for global scope struct Node *head = NULL; //Function to insert a node at the beginning of the linked list void push( struct Node *node, int new_data) { //create a new node struct Node * new = malloc ( sizeof ( struct Node)); //assign data to the new node new -> data = new_data; //add the node at the beginning and update the head new -> next = head; head = new ; } //Function to find product of the nodes of the given linked list int productOfNodes() { //Node to traverse the linked list struct Node *tr = head; //initializing the variable product to store the product int product = 1; //traversing the list and finding the product while (tr != NULL) { product *= tr -> data; tr = tr -> next; } return product; } int main() { //create a linked list 7 -> 6 -> 8 -> 4 -> 1 push(head, 1); push(head, 4); push(head, 8); push(head, 6); push(head, 7); //calling function productOfNodes and displaying output int ans = productOfNodes(); printf ( "Product = %d" , ans); return 0; } |
Java
// Java implementation to find the product of nodes of a // linked list import java.util.*; // A linked List node class Node { int data; Node next; // Constructor to initialize a new node Node( int data) { this .data = data; this .next = null ; } } // Main class to implement the linked list and its // operations class LinkedList { Node head; // Function to insert a node at the beginning of the // linked list Node push( int data) { Node new_node = new Node(data); // link the old list to the new node new_node.next = head; // move the head to point to the new node head = new_node; return head; } // Function to find the product of nodes of the given // linked list int productOfNodes() { Node ptr = head; int product = 1 ; // Variable to store product // Traverse the list and calculate the product while (ptr != null ) { product *= ptr.data; ptr = ptr.next; } // Return the product return product; } // Driver Code public static void main(String args[]) { LinkedList llist = new LinkedList(); // create linked list 7->6->8->4->1 llist.push( 1 ); llist.push( 4 ); llist.push( 8 ); llist.push( 6 ); llist.push( 7 ); System.out.println( "Product = " + llist.productOfNodes()); } } |
Python3
# Python3 implementation to find the product of # nodes of the Linked List import math # A linked List node class Node: def __init__( self , data): self .data = data self . next = None # Function to insert a node at the # beginning of the linked list def push(head, data): if not head: # Return new node return Node(data) # allocate node new_node = Node(data) # link the old list to the new node new_node. next = head # move the head to point to the new node head = new_node return head # Function to find the product of # nodes of the given linked list def productOfNodes(head): # Pointer to traverse the list ptr = head product = 1 # Variable to store product # Traverse the list and # calculate the product while (ptr): product * = ptr.data ptr = ptr. next # Return the product return product # Driver Code if __name__ = = '__main__' : head = None # create linked list 7->6->8->4->1 head = push(head, 7 ) head = push(head, 6 ) head = push(head, 8 ) head = push(head, 4 ) head = push(head, 1 ) print ( "Product = {}" . format (productOfNodes(head))) # This Code is Contributed By Vikash Kumar 37 |
C#
// C# implementation to find the product of // nodes of the Linked List using System; class GFG { // A Linked list node public class Node { public int data; public Node next; }; // Function to insert a node at the // beginning of the linked list static Node push(Node head_ref, int new_data) { // allocate node / Node new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list to the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref; } // Function to find the product of // nodes of the given linked list static int productOfNodes(Node head) { // Pointer to traverse the list Node ptr = head; int product = 1; // Variable to store product // Traverse the list and // calculate the product while (ptr != null ) { product *= ptr.data; ptr = ptr.next; } // Return the product return product; } // Driver Code public static void Main(String[] args) { Node head = null ; // create linked list 7.6.8.4.1 head = push(head, 7); head = push(head, 6); head = push(head, 8); head = push(head, 4); head = push(head, 1); Console.WriteLine( "Product = " + productOfNodes(head)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript implementation to find the product of // nodes of the Linked List // A Linked list node class Node { constructor(val) { this .data = val; this .next = null ; } } // Function to insert a node at the // beginning of the linked list function push(head_ref , new_data) { // allocate node / var new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list to the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref; } // Function to find the product of // nodes of the given linked list function productOfNodes(head) { // Pointer to traverse the list var ptr = head; var product = 1; // Variable to store product // Traverse the list and // calculate the product while (ptr != null ) { product *= ptr.data; ptr = ptr.next; } // Return the product return product; } // Driver Code var head = null ; // create linked list 7.6.8.4.1 head = push(head, 7); head = push(head, 6); head = push(head, 8); head = push(head, 4); head = push(head, 1); document.write( "Product = " + productOfNodes(head)); // This code contributed by aashish1995 </script> |
Output
Product = 1344
Complexity Analysis:
- Time Complexity: O(N), where N is the number of nodes in the linked list.
- Auxiliary Space: O(1)
Recursive Approach:
- If the head pointer is NULL, return 1.
- Otherwise, recursively call the productOfNodes function on the next node of the linked list.
- Multiply the data value of the current node with the return value from the recursive call.
- Return the final product.
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; // A Linked list node struct Node { int data; struct Node* next; }; // Function to insert a node at the // beginning of the linked list void push( struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Function to find the product of // nodes of the given linked list int productOfNodes( struct Node* head) { if (head == NULL) { // base case return 1; } else { return (head->data * productOfNodes(head->next)); } } // Driver Code int main() { struct Node* head = NULL; // create linked list 7->6->8->4->1 push(&head, 7); push(&head, 6); push(&head, 8); push(&head, 4); push(&head, 1); cout << "Product = " << productOfNodes(head); return 0; } |
Java
class Node { int data; Node next; Node( int data) { this .data = data; this .next = null ; } } public class Main { // Function to insert a node at the // beginning of the linked list static Node push(Node headRef, int newData) { Node newNode = new Node(newData); newNode.next = headRef; headRef = newNode; return headRef; } // Function to find the product of // nodes of the given linked list static int productOfNodes(Node head) { if (head == null ) { // base case return 1 ; } else { return (head.data * productOfNodes(head.next)); } } // Driver Code public static void main(String[] args) { Node head = null ; // create linked list 7->6->8->4->1 head = push(head, 7 ); head = push(head, 6 ); head = push(head, 8 ); head = push(head, 4 ); head = push(head, 1 ); System.out.println( "Product = " + productOfNodes(head)); } } // This code is contributed by Samim Hossain Mondal |
Python
# A Linked list node class Node: def __init__( self , data): self .data = data self . next = None # Function to insert a node at the # beginning of the linked list def push(head_ref, new_data): new_node = Node(new_data) new_node. next = head_ref return new_node # Function to find the product of # nodes of the given linked list def product_of_nodes(head): if head is None : # base case return 1 else : return head.data * product_of_nodes(head. next ) # Driver Code if __name__ = = "__main__" : head = None # create linked list 7->6->8->4->1 head = push(head, 7 ) head = push(head, 6 ) head = push(head, 8 ) head = push(head, 4 ) head = push(head, 1 ) print ( "Product =" , product_of_nodes(head)) |
C#
using System; class Node { public int data; public Node next; public Node( int data) { this .data = data; this .next = null ; } } public class LinkedListOperations { // Function to insert a node at the // beginning of the linked list static Node Push(Node headRef, int newData) { Node newNode = new Node(newData); newNode.next = headRef; headRef = newNode; return headRef; } // Function to find the product of // nodes of the given linked list static int ProductOfNodes(Node head) { if (head == null ) // base case { return 1; } else { return (head.data * ProductOfNodes(head.next)); } } // Entry point of the program public static void Main( string [] args) { Node head = null ; // create linked list 7->6->8->4->1 head = Push(head, 7); head = Push(head, 6); head = Push(head, 8); head = Push(head, 4); head = Push(head, 1); Console.WriteLine( "Product = " + ProductOfNodes(head)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
// Javascript implementation to find the product of // nodes of the Linked List // A Linked list node class Node { constructor(val) { this .data = val; this .next = null ; } } // Function to insert a node at the // beginning of the linked list function push(head_ref , new_data) { // allocate node / var new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list to the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref; } // Function to find the product of // nodes of the given linked list function productOfNodes(head) { if (head == null ){ return 1; } else { return (head.data * productOfNodes(head.next)); } } // Driver Code var head = null ; // create linked list 7.6.8.4.1 head = push(head, 7); head = push(head, 6); head = push(head, 8); head = push(head, 4); head = push(head, 1); console.log( "Product = " + productOfNodes(head)); // THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL |
Output:
Product = 1344
Time Complexity: O(n), where n is the number of nodes in the linked list. This is because the function must visit each node in the linked list exactly once.
Auxiliary Space: O(n), where n is the number of nodes in the linked list. This is because the recursive calls build up a chain of stack frames, one for each node in the linked list.