Given a linked list that contains a series of numbers separated by “0”. Multiply them and store them in the linked list in place.
Note: There will not be continuous zeros in the input.
Examples:
Input : 1->2->3->0->5->4->0->3->2->0 Output : 6->20->6 Input : 1->2->3->4 Output : 1->2->3->4
Approach:
- Start iterating over nodes of the linked list.
- Iterate while temp.data !=0, and multiply these data into a variable ‘prod’.
- When you encounter 0 as the node’s data, change pointers of previous nodes.
Below is the implementation of the above approach:
C++
// C++ program to in-place product linked list// nodes between 0s#include<bits/stdc++.h>using namespace std;// Linked List Nodestruct Node { int data; Node* next; Node(int d) { data = d; next = NULL; }};// Function to traverse and print Linked List void printList(Node* head) { while (head->next != NULL) { cout<<head->data <<"-> "; head = head->next; } cout << head->data << "\n"; }// Function to in-place product linked list// nodes between 0s // Function to store numbers till 0 void inPlaceStore(Node* head) { if (head->data == 0) { head = head->next; } // To store modified list Node* res = head; // Traverse linked list and keep // adding nodes between 0s. Node* temp = head; int prod = 1; while (temp != NULL) { // loop to product the data of nodes till // it encounters 0 if (temp->data != 0) { prod *= temp->data; temp = temp->next; } // If we encounters 0, we need // to update next pointers else { res->data = prod; res->next = temp->next; temp = temp->next; res = res->next; prod = 1; } } // For the last segment res->data = prod; res->next = temp; printList(head); } // Driver Code int main() { Node *head = new Node(3); head->next = new Node(2); head->next->next = new Node(0); head->next->next->next = new Node(4); head->next->next->next->next = new Node(5); head->next->next->next->next->next = new Node(0); head->next->next->next->next->next->next = new Node(6); head->next->next->next->next->next->next->next = new Node(7); inPlaceStore(head); return 0; } // This code is contributed by Arnab Kundu |
Java
// Java program to in-place product linked list// nodes between 0s // Linked List Nodeclass Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; }} // Function to in-place product linked list// nodes between 0spublic class inPlaceStoreLL { // Function to store numbers till 0 static void inPlaceStore(Node head) { if (head.data == 0) { head = head.next; } // To store modified list Node res = head; // Traverse linked list and keep // adding nodes between 0s. Node temp = head; int prod = 1; while (temp != null) { // loop to product the data of nodes till // it encounters 0 if (temp.data != 0) { prod *= temp.data; temp = temp.next; } // If we encounters 0, we need // to update next pointers else { res.data = prod; res.next = temp.next; temp = temp.next; res = res.next; prod = 1; } } // For the last segment res.data = prod; res.next = temp; printList(head); } // Function to traverse and print Linked List static void printList(Node head) { while (head.next != null) { System.out.print(head.data + "-> "); head = head.next; } System.out.println(head.data); } // Driver Code public static void main(String[] args) { Node head = new Node(3); head.next = new Node(2); head.next.next = new Node(0); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next.next = new Node(7); inPlaceStore(head); }} |
Python3
# Python3 program to in-place # product linked list nodes between 0simport math# Linked List Nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to traverse and print Linked Listdef printList(head): while (head.next != None): print(head.data, end = "->") head = head.next print(head.data) print()# Function to in-place product linked list# nodes between 0s# Function to store numbers till 0def inPlaceStore(head): if (head.data == 0): head = head.next # To store modified list res = head # Traverse linked list and keep # adding nodes between 0s. temp = head prod = 1 while (temp != None): # loop to product the data of nodes till # it encounters 0 if (temp.data != 0): prod = prod * temp.data temp = temp.next # If we encounters 0, we need # to update next pointers else: res.data = prod res.next = temp.next temp = temp.next res = res.next prod = 1 # For the last segment res.data = prod res.next = temp printList(head)# Driver Codeif __name__=='__main__': head = Node(3) head.next = Node(2) head.next.next = Node(0) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(0) head.next.next.next.next.next.next = Node(6) head.next.next.next.next.next.next.next = Node(7) inPlaceStore(head) # This code is contributed by Srathore |
C#
// C# program to in-place product linked list // nodes between 0s using System;// Linked List Node public class Node { public int data; public Node next; public Node(int data) { this.data = data; this.next = null; } } // Function to in-place product linked list // nodes between 0s public class inPlaceStoreLL { // Function to store numbers till 0 static void inPlaceStore(Node head) { if (head.data == 0) { head = head.next; } // To store modified list Node res = head; // Traverse linked list and keep // adding nodes between 0s. Node temp = head; int prod = 1; while (temp != null) { // loop to product the data of nodes till // it encounters 0 if (temp.data != 0) { prod *= temp.data; temp = temp.next; } // If we encounters 0, we need // to update next pointers else { res.data = prod; res.next = temp.next; temp = temp.next; res = res.next; prod = 1; } } // For the last segment res.data = prod; res.next = temp; printList(head); } // Function to traverse and print Linked List static void printList(Node head) { while (head.next != null) { Console.Write(head.data + "-> "); head = head.next; } Console.WriteLine(head.data); } // Driver Code public static void Main(String[] args) { Node head = new Node(3); head.next = new Node(2); head.next.next = new Node(0); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next.next = new Node(7); inPlaceStore(head); } } // This code has been contributed by 29AjayKumar |
Javascript
<script>// javascript program to in-place product linked list// nodes between 0s// Linked List Node class Node { constructor(data) { this.data = data; this.next = null; } } // Function to in-place product linked list // nodes between 0s // Function to store numbers till 0 function inPlaceStore(head) { if (head.data == 0) { head = head.next; } // To store modified list var res = head; // Traverse linked list and keep // adding nodes between 0s. var temp = head; var prod = 1; while (temp != null) { // loop to product the data of nodes till // it encounters 0 if (temp.data != 0) { prod *= temp.data; temp = temp.next; } // If we encounters 0, we need // to update next pointers else { res.data = prod; res.next = temp.next; temp = temp.next; res = res.next; prod = 1; } } // For the last segment res.data = prod; res.next = temp; printList(head); } // Function to traverse and print Linked List function printList(head) { while (head.next != null) { document.write(head.data + "-> "); head = head.next; } document.write(head.data); } // Driver Code var head = new Node(3); head.next = new Node(2); head.next.next = new Node(0); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(0); head.next.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next.next = new Node(7); inPlaceStore(head);// This code contributed by Rajput-Ji</script> |
Output
6-> 20-> 42
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!
