Dada una lista enlazada que contiene una serie de números separados por “0”. Multiplícalos y guárdalos en la lista enlazada en su lugar.
Nota: No habrá ceros continuos en la entrada.
Ejemplos :
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
Enfoque :
- Comience a iterar sobre los Nodes de la lista vinculada.
- Iterar while temp.data !=0, y multiplicar estos datos en una variable ‘prod’.
- Cuando encuentre 0 como datos del Node, cambie los punteros de los Nodes anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to in-place product linked list
// nodes between 0s
#include<bits/stdc++.h>
using namespace std;
// Linked List Node
struct 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 Node
class Node {
int data;
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) {
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 0s import math # Linked List Node class Node: def __init__(self, data): self.data = data self.next = None # Function to traverse and print Linked List def 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 0 def 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 Code if __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>
Producción:
6-> 20-> 42
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA