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
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 nodestruct Node { int data; struct Node* next;};// Function to insert a node at the// beginning of the linked listvoid 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 listint 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 Codeint 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 nodestruct Node{ int data; struct Node *next;};//Creating node head for global scopestruct Node *head = NULL;//Function to insert a node at the beginning of the linked listvoid 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 listint 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 listimport java.util.*;// A linked List nodeclass 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// operationsclass 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 Listimport math# A linked List nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to insert a node at the# beginning of the linked listdef 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 listdef 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 Codeif __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 Listusing 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 nodeclass 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 listvar 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 nodestruct Node { int data; struct Node* next;};// Function to insert a node at the// beginning of the linked listvoid 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 listint productOfNodes(struct Node* head){ if (head == NULL) { // base case return 1; } else { return (head->data * productOfNodes(head->next)); }}// Driver Codeint 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 nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to insert a node at the# beginning of the linked listdef 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 listdef product_of_nodes(head): if head is None: # base case return 1 else: return head.data * product_of_nodes(head.next)# Driver Codeif __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 nodeclass Node { constructor(val) { this.data = val; this.next = null; }}// Function to insert a node at the// beginning of the linked listfunction 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 listfunction productOfNodes(head) { if(head == null){ return 1; }else{ return (head.data * productOfNodes(head.next)); }}// Driver Codevar head = null;// create linked list 7.6.8.4.1head = 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.
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!
