Dada una lista enlazada y un número N. Encuentra el producto de los últimos n Nodes de la lista enlazada.
Restricciones: 0 <= N <= número de Nodes en la lista enlazada.
Ejemplos :
Input : List = 10->6->8->4->12, N = 2
Output : 48
Explanation : Product of last two nodes:
12 * 4 = 48
Input : List = 15->7->9->5->16->14, N = 4
Output : 10080
Explanation : Product of last four nodes:
9 * 5 * 16 * 14 = 10080
Método 1: (Enfoque iterativo usando la pila definida por el usuario) Atraviese los Nodes de izquierda a derecha. Mientras atraviesa, empuje los Nodes a una pila definida por el usuario. Luego extrae los n valores superiores de la pila y encuentra su producto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the product of last
// 'n' nodes of the Linked List
#include <bits/stdc++.h>
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;
}
// utility function to find the product of last 'n' nodes
int productOfLastN_NodesUtil(struct Node* head, int n)
{
// if n == 0
if (n <= 0)
return 0;
stack<int> st;
int prod = 1;
// traverses the list from left to right
while (head != NULL) {
// push the node's data onto the stack 'st'
st.push(head->data);
// move to next node
head = head->next;
}
// pop 'n' nodes from 'st' and
// add them
while (n--) {
prod *= st.top();
st.pop();
}
// required product
return prod;
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// create linked list 10->6->8->4->12
push(&head, 12);
push(&head, 4);
push(&head, 8);
push(&head, 6);
push(&head, 10);
int n = 2;
cout << productOfLastN_NodesUtil(head, n);
return 0;
}
Java
// Java implementation to find the product
// of last 'n' nodes of the Linked List
import java.util.*;
class GFG
{
/* A Linked list node */
static class Node
{
int data;
Node next;
};
static Node head;
// function to insert a node at the
// beginning of the linked list
static void 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;
head = head_ref;
}
// utility function to find the product
// of last 'n' nodes
static int productOfLastN_NodesUtil(Node head,
int n)
{
// if n == 0
if (n <= 0)
return 0;
Stack<Integer> st = new Stack<Integer>();
int prod = 1;
// traverses the list from left to right
while (head != null)
{
// push the node's data
// onto the stack 'st'
st.push(head.data);
// move to next node
head = head.next;
}
// pop 'n' nodes from 'st' and
// add them
while (n-- >0)
{
prod *= st.peek();
st.pop();
}
// required product
return prod;
}
// Driver Code
public static void main(String[] args)
{
head = null;
// create linked list 10->6->8->4->12
push(head, 12);
push(head, 4);
push(head, 8);
push(head, 6);
push(head, 10);
int n = 2;
System.out.println(productOfLastN_NodesUtil(head, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to find the product # of last 'n' nodes of the Linked List # Link list node class Node: def __init__(self, data): self.data = data self.next = next head = None # function to insert a node at the # beginning of the linked list def push(head_ref, new_data): global head # allocate node new_node = Node(0) # 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 head = head_ref # utility function to find the product # of last 'n' nodes def productOfLastN_NodesUtil(head, n): # if n == 0 if (n <= 0): return 0 st = [] prod = 1 # traverses the list from left to right while (head != None) : # push the node's data # onto the stack 'st' st.append(head.data) # move to next node head = head.next # pop 'n' nodes from 'st' and # add them while (n > 0) : n = n - 1 prod *= st[-1] st.pop() # required product return prod # Driver Code head = None # create linked list 10->6->8->4->12 push(head, 12) push(head, 4) push(head, 8) push(head, 6) push(head, 10) n = 2 print(productOfLastN_NodesUtil(head, n)) # This code is contributed by Arnab Kundu
C#
// C# implementation to find the product
// of last 'n' 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;
}
// utility function to find the product
// of last 'n' nodes
static int productOfLastN_NodesUtil(Node head,
int n)
{
// if n == 0
if (n <= 0)
return 0;
int prod = 1, len = 0;
Node temp = head;
// calculate the length of the linked list
while (temp != null)
{
len++;
temp = temp.next;
}
// count of first (len - n) nodes
int c = len - n;
temp = head;
// just traverse the 1st 'c' nodes
while (temp != null && c-- >0)
// move to next node
temp = temp.next;
// now traverse the last 'n' nodes
// and add them
while (temp != null)
{
// accumulate node's data to sum
prod *= temp.data;
// move to next node
temp = temp.next;
}
// required product
return prod;
}
// Driver Code
public static void Main(String[] args)
{
Node head = null;
// create linked list 10.6.8.4.12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
int n = 2;
Console.Write(productOfLastN_NodesUtil(head, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation to find the product
// of last 'n' nodes of the Linked List
/* A Linked list node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var head;
// 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;
head = head_ref;
}
// utility function to find the product
// of last 'n' nodes
function productOfLastN_NodesUtil(head , n) {
// if n == 0
if (n <= 0)
return 0;
var st = [];
var prod = 1;
// traverses the list from left to right
while (head != null) {
// push the node's data
// onto the stack 'st'
st.push(head.data);
// move to next node
head = head.next;
}
// pop 'n' nodes from 'st' and
// add them
while (n-- > 0) {
prod *= st.pop();
}
// required product
return prod;
}
// Driver Code
head = null;
// create linked list 10->6->8->4->12
push(head, 12);
push(head, 4);
push(head, 8);
push(head, 6);
push(head, 10);
var n = 2;
document.write(productOfLastN_NodesUtil(head, n));
// This code contributed by aashish1995
</script>
Producción:
48
Complejidad del tiempo : O(n)
Método 2: (Enfoque recursivo usando la pila de llamadas del sistema) Atraviese recursivamente la lista enlazada hasta el final. Ahora, durante el retorno de las llamadas a funciones, multiplique los últimos n Nodes. El producto se puede acumular en alguna variable pasada por referencia a la función oa alguna variable global.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the product of
// last 'n' nodes of the Linked List
#include <bits/stdc++.h>
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 recursively find the product of last
// 'n' nodes of the given linked list
void productOfLastN_Nodes(struct Node* head, int* n,
int* prod)
{
// if head = NULL
if (!head)
return;
// recursively traverse the remaining nodes
productOfLastN_Nodes(head->next, n, prod);
// if node count 'n' is greater than 0
if (*n > 0) {
// accumulate sum
*prod = *prod * head->data;
// reduce node count 'n' by 1
--*n;
}
}
// utility function to find the product of last 'n' nodes
int productOfLastN_NodesUtil(struct Node* head, int n)
{
// if n == 0
if (n <= 0)
return 0;
int prod = 1;
// find the sum of last 'n' nodes
productOfLastN_Nodes(head, &n, &prod);
// required product
return prod;
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// create linked list 10->6->8->4->12
push(&head, 12);
push(&head, 4);
push(&head, 8);
push(&head, 6);
push(&head, 10);
int n = 2;
cout << productOfLastN_NodesUtil(head, n);
return 0;
}
Java
// Java implementation to find the product of
// last 'n' nodes of the Linked List
class GFG{
static int n, prod;
/* A Linked list node */
static class Node {
int data;
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 recursively find the product of last
// 'n' nodes of the given linked list
static void productOfLastN_Nodes(Node head)
{
// if head = null
if (head==null)
return;
// recursively traverse the remaining nodes
productOfLastN_Nodes(head.next);
// if node count 'n' is greater than 0
if (n > 0) {
// accumulate sum
prod = prod * head.data;
// reduce node count 'n' by 1
--n;
}
}
// utility function to find the product of last 'n' nodes
static int productOfLastN_NodesUtil(Node head)
{
// if n == 0
if (n <= 0)
return 0;
prod = 1;
// find the sum of last 'n' nodes
productOfLastN_Nodes(head);
// required product
return prod;
}
// Driver program to test above
public static void main(String[] args)
{
Node head = null;
// create linked list 10->6->8->4->12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
n = 2;
System.out.print(productOfLastN_NodesUtil(head));
}
}
//This code is contributed by 29AjayKumar
Python3
# Python implementation to find the product of # last 'n' Nodes of the Linked List n, prod = 0, 0; ''' A Linked list Node ''' class Node: def __init__(self, data): self.data = data self.next = next # function to insert a Node at the # beginning of the linked list def push(head_ref, new_data): ''' allocate Node ''' new_Node = Node(0); ''' 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 recursively find the product of last # 'n' Nodes of the given linked list def productOfLastN_Nodes(head): global n, prod; # if head = None if (head == None): return; # recursively traverse the remaining Nodes productOfLastN_Nodes(head.next); # if Node count 'n' is greater than 0 if (n > 0): # accumulate sum prod = prod * head.data; # reduce Node count 'n' by 1 n -= 1; # utility function to find the product of last 'n' Nodes def productOfLastN_NodesUtil(head): global n,prod; # if n == 0 if (n <= 0): return 0; prod = 1; # find the sum of last 'n' Nodes productOfLastN_Nodes(head); # required product return prod; # Driver program to test above if __name__ == '__main__': head = None; n = 2; # create linked list 10->6->8->4->12 head = push(head, 12); head = push(head, 4); head = push(head, 8); head = push(head, 6); head = push(head, 10); print(productOfLastN_NodesUtil(head)); # This code is contributed by 29AjayKumar
C#
// C# implementation to find the product of
// last 'n' nodes of the Linked List
using System;
public class GFG{
static int n, prod;
/* 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 recursively find the product of last
// 'n' nodes of the given linked list
static void productOfLastN_Nodes(Node head)
{
// if head = null
if (head==null)
return;
// recursively traverse the remaining nodes
productOfLastN_Nodes(head.next);
// if node count 'n' is greater than 0
if (n > 0) {
// accumulate sum
prod = prod * head.data;
// reduce node count 'n' by 1
--n;
}
}
// utility function to find the product of last 'n' nodes
static int productOfLastN_NodesUtil(Node head)
{
// if n == 0
if (n <= 0)
return 0;
prod = 1;
// find the sum of last 'n' nodes
productOfLastN_Nodes(head);
// required product
return prod;
}
// Driver program to test above
public static void Main(String[] args)
{
Node head = null;
// create linked list 10->6->8->4->12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
n = 2;
Console.Write(productOfLastN_NodesUtil(head));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation to find the product of
// last 'n' nodes of the Linked List
var n, prod;
/* 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 recursively find the product of last
// 'n' nodes of the given linked list
function productOfLastN_Nodes(head) {
// if head = null
if (head == null)
return;
// recursively traverse the remaining nodes
productOfLastN_Nodes(head.next);
// if node count 'n' is greater than 0
if (n > 0) {
// accumulate sum
prod = prod * head.data;
// reduce node count 'n' by 1
--n;
}
}
// utility function to find the product of last 'n' nodes
function productOfLastN_NodesUtil(head) {
// if n == 0
if (n <= 0)
return 0;
prod = 1;
// find the sum of last 'n' nodes
productOfLastN_Nodes(head);
// required product
return prod;
}
// Driver program to test above
var head = null;
// create linked list 10->6->8->4->12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
n = 2;
document.write(productOfLastN_NodesUtil(head));
// This code contributed by gauravrajput1
</script>
Producción:
48
Complejidad temporal: O(n)
Método 3 (Invertir la lista enlazada) :
Los siguientes son los pasos:
- Invierta la lista enlazada dada.
- Atraviese los primeros n Nodes de la lista enlazada invertida.
- Al atravesarlos multiplícalos.
- Invierta la lista enlazada a su orden original.
- Devolver el producto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the product of last
// 'n' nodes of the Linked List
#include <bits/stdc++.h>
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;
}
void reverseList(struct Node** head_ref)
{
struct Node *current, *prev, *next;
current = *head_ref;
prev = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
// utility function to find the product of last 'n' nodes
int productOfLastN_NodesUtil(struct Node* head, int n)
{
// if n == 0
if (n <= 0)
return 0;
// reverse the linked list
reverseList(&head);
int prod = 1;
struct Node* current = head;
// traverse the 1st 'n' nodes of the reversed
// linked list and product them
while (current != NULL && n--) {
// accumulate node's data to 'sum'
prod *= current->data;
// move to next node
current = current->next;
}
// reverse back the linked list
reverseList(&head);
// required product
return prod;
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// create linked list 10->6->8->4->12
push(&head, 12);
push(&head, 4);
push(&head, 8);
push(&head, 6);
push(&head, 10);
int n = 2;
cout << productOfLastN_NodesUtil(head, n);
return 0;
}
Java
// Java implementation to find the product of last
// 'n' nodes of the Linked List
class GFG
{
/* A Linked list node */
static class Node
{
int data;
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;
}
static Node reverseList(Node head_ref)
{
Node current, prev, next;
current = head_ref;
prev = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head_ref = prev;
return head_ref;
}
// utility function to find the product of last 'n' nodes
static int productOfLastN_NodesUtil(Node head, int n)
{
// if n == 0
if (n <= 0)
return 0;
// reverse the linked list
head = reverseList(head);
int prod = 1;
Node current = head;
// traverse the 1st 'n' nodes of the reversed
// linked list and product them
while (current != null && n-- >0)
{
// accumulate node's data to 'sum'
prod *= current.data;
// move to next node
current = current.next;
}
// reverse back the linked list
head = reverseList(head);
// required product
return prod;
}
// Driver program to test above
public static void main(String[] args)
{
Node head = null;
// create linked list 10.6.8.4.12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
int n = 2;
System.out.print(productOfLastN_NodesUtil(head, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find the product of last # 'n' nodes of the Linked List ''' 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): ''' allocate node ''' new_node = Node(new_data); ''' 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 def reverseList(head_ref): next = None current = head_ref; prev = None; while (current != None): next = current.next; current.next = prev; prev = current; current = next; head_ref = prev return head_ref # utility function to find the product of last 'n' nodes def productOfLastN_NodesUtil(head, n): # if n == 0 if (n <= 0): return 0; # reverse the linked list head = reverseList(head); prod = 1; current = head; # traverse the 1st 'n' nodes of the reversed # linked list and product them while (current != None and n): n -= 1 # accumulate node's data to 'sum' prod *= current.data; # move to next node current = current.next; # reverse back the linked list head = reverseList(head); # required product return prod; # Driver program to test above if __name__=='__main__': head = None; # create linked list 10.6.8.4.12 head = push(head, 12); head = push(head, 4); head = push(head, 8); head = push(head, 6); head = push(head, 10); n = 2; print(productOfLastN_NodesUtil(head, n)) # This code is contributed by rutvik_56
C#
// C# implementation to find
// the product of last 'n' nodes
// of the Linked List
using System;
class GFG
{
/* A Linked list node */
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;
}
static Node reverseList(Node head_ref)
{
Node current, prev, next;
current = head_ref;
prev = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head_ref = prev;
return head_ref;
}
// utility function to find
// the product of last 'n' nodes
static int productOfLastN_NodesUtil(Node head, int n)
{
// if n == 0
if (n <= 0)
return 0;
// reverse the linked list
head = reverseList(head);
int prod = 1;
Node current = head;
// traverse the 1st 'n' nodes of the reversed
// linked list and product them
while (current != null && n-- >0)
{
// accumulate node's data to 'sum'
prod *= current.data;
// move to next node
current = current.next;
}
// reverse back the linked list
head = reverseList(head);
// required product
return prod;
}
// Driver Code
public static void Main(String[] args)
{
Node head = null;
// create linked list 10.6.8.4.12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
int n = 2;
Console.Write(productOfLastN_NodesUtil(head, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript implementation to find the product of last
// 'n' 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 reverseList(head_ref) {
var current, prev, next;
current = head_ref;
prev = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head_ref = prev;
return head_ref;
}
// utility function to find the product of last 'n' nodes
function productOfLastN_NodesUtil(head , n) {
// if n == 0
if (n <= 0)
return 0;
// reverse the linked list
head = reverseList(head);
var prod = 1;
var current = head;
// traverse the 1st 'n' nodes of the reversed
// linked list and product them
while (current != null && n-- > 0) {
// accumulate node's data to 'sum'
prod *= current.data;
// move to next node
current = current.next;
}
// reverse back the linked list
head = reverseList(head);
// required product
return prod;
}
// Driver program to test above
var head = null;
// create linked list 10.6.8.4.12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
var n = 2;
document.write(productOfLastN_NodesUtil(head, n));
// This code contributed by aashish1995
</script>
Producción:
48
Complejidad temporal: O(n)
Método 4 (usando la longitud de la lista enlazada) :
Los siguientes son los pasos:
- Calcule la longitud de la lista enlazada dada. Que sea len.
- Primero recorra los Nodes (len – n) desde el principio.
- Luego, recorra los n Nodes restantes y, mientras los recorre, prodúzcalos.
- Devolver el producto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the product of last
// 'n' nodes of the Linked List
#include <bits/stdc++.h>
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;
}
// utility function to find the product of last 'n' nodes
int productOfLastN_NodesUtil(struct Node* head, int n)
{
// if n == 0
if (n <= 0)
return 0;
int prod = 1, len = 0;
struct Node* temp = head;
// calculate the length of the linked list
while (temp != NULL) {
len++;
temp = temp->next;
}
// count of first (len - n) nodes
int c = len - n;
temp = head;
// just traverse the 1st 'c' nodes
while (temp != NULL && c--)
// move to next node
temp = temp->next;
// now traverse the last 'n' nodes and add them
while (temp != NULL) {
// accumulate node's data to sum
prod *= temp->data;
// move to next node
temp = temp->next;
}
// required product
return prod;
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// create linked list 10->6->8->4->12
push(&head, 12);
push(&head, 4);
push(&head, 8);
push(&head, 6);
push(&head, 10);
int n = 2;
cout << productOfLastN_NodesUtil(head, n);
return 0;
}
Java
// Java implementation to find the product of last
// 'n' nodes of the Linked List
class GFG
{
/* A Linked list node */
static class Node
{
int data;
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;
}
// utility function to find the product of last 'n' nodes
static int productOfLastN_NodesUtil(Node head, int n)
{
// if n == 0
if (n <= 0)
return 0;
int prod = 1, len = 0;
Node temp = head;
// calculate the length of the linked list
while (temp != null)
{
len++;
temp = temp.next;
}
// count of first (len - n) nodes
int c = len - n;
temp = head;
// just traverse the 1st 'c' nodes
while (temp != null && c-- >0)
// move to next node
temp = temp.next;
// now traverse the last 'n' nodes and add them
while (temp != null)
{
// accumulate node's data to sum
prod *= temp.data;
// move to next node
temp = temp.next;
}
// required product
return prod;
}
// Driver program to test above
public static void main(String[] args)
{
Node head = null;
// create linked list 10.6.8.4.12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
int n = 2;
System.out.print(productOfLastN_NodesUtil(head, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to find the product of last # 'n' nodes of the Linked List ''' A Linked list node ''' class Node: def __init__(self): self.data = 0 self.next = None # function to insert a node at the # beginning of the linked list def push(head_ref, new_data): ''' allocate node ''' new_node = 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; # utility function to find the product of last 'n' nodes def productOfLastN_NodesUtil(head, n): # if n == 0 if (n <= 0): return 0; prod = 1 len = 0; temp = head; # calculate the length of the linked list while (temp != None): len += 1 temp = temp.next; # count of first (len - n) nodes c = len - n; temp = head; # just traverse the 1st 'c' nodes while (temp != None and c > 0): c -= 1 # move to next node temp = temp.next; # now traverse the last 'n' nodes and add them while (temp != None): # accumulate node's data to sum prod *= temp.data; # move to next node temp = temp.next; # required product return prod; # Driver program to test above if __name__=='__main__': head = None; # create linked list 10.6.8.4.12 head = push(head, 12); head = push(head, 4); head = push(head, 8); head = push(head, 6); head = push(head, 10); n = 2; print(productOfLastN_NodesUtil(head, n)); # This code is contributed by Pratham76
C#
// C# implementation to find the product of last
// 'n' nodes of the Linked List
using System;
public 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;
}
// utility function to find the product of last 'n' nodes
static int productOfLastN_NodesUtil(Node head, int n)
{
// if n == 0
if (n <= 0)
return 0;
int prod = 1, len = 0;
Node temp = head;
// calculate the length of the linked list
while (temp != null)
{
len++;
temp = temp.next;
}
// count of first (len - n) nodes
int c = len - n;
temp = head;
// just traverse the 1st 'c' nodes
while (temp != null && c-- >0)
// move to next node
temp = temp.next;
// now traverse the last 'n' nodes and add them
while (temp != null)
{
// accumulate node's data to sum
prod *= temp.data;
// move to next node
temp = temp.next;
}
// required product
return prod;
}
// Driver program to test above
public static void Main(String[] args)
{
Node head = null;
// create linked list 10.6.8.4.12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
int n = 2;
Console.Write(productOfLastN_NodesUtil(head, n));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find the product of last
// 'n' nodes of the Linked List
/* A Linked list node */
class Node
{
constructor()
{
this.data = 0;
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;
}
// utility function to find the product of last 'n' nodes
function productOfLastN_NodesUtil(head, n)
{
// if n == 0
if (n <= 0)
return 0;
var prod = 1, len = 0;
var temp = head;
// calculate the length of the linked list
while (temp != null)
{
len++;
temp = temp.next;
}
// count of first (len - n) nodes
var c = len - n;
temp = head;
// just traverse the 1st 'c' nodes
while (temp != null && c-- >0)
// move to next node
temp = temp.next;
// now traverse the last 'n' nodes and add them
while (temp != null)
{
// accumulate node's data to sum
prod *= temp.data;
// move to next node
temp = temp.next;
}
// required product
return prod;
}
// Driver program to test above
var head = null;
// create linked list 10.6.8.4.12
head = push(head, 12);
head = push(head, 4);
head = push(head, 8);
head = push(head, 6);
head = push(head, 10);
var n = 2;
document.write(productOfLastN_NodesUtil(head, n));
</script>
Producción:
48
Complejidad del tiempo : O(n)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA