Dada una lista enlazada individualmente que contiene N Nodes, la tarea es realizar las siguientes operaciones en los Nodes de Fibonacci presentes en ella:
- Imprime todos los Nodes de Fibonacci presentes en la lista enlazada individualmente .
- Encuentre el recuento total de Nodes de Fibonacci presentes en la lista de enlaces individuales .
- Encuentre los Nodes mínimo y máximo de Fibonacci.
- Quite todos los Nodes de Fibonacci de la lista enlazada individualmente .
Ejemplos:
Entrada: LL = 15 -> 16 -> 8 -> 6 -> 13
Salida:
Nodes de Fibonacci = 8, 13
Número de Nodes de Fibonacci = 2
Nodes de Fibonacci mínimos en la lista = 8
Nodes de Fibonacci máximos en la lista = 13
Lista después de eliminar Nodes de Fibonacci = 15 -> 16 -> 6
Entrada: LL = 5 -> 3 -> 4 -> 2 -> 9
Salida:
Nodes de Fibonacci = 5, 3, 2
Número de Nodes de Fibonacci = 3
Nodes de Fibonacci mínimos en la lista = 2
Nodes máximos de Fibonacci en la lista = 5
Lista después de eliminar los Nodes de Fibonacci = 4 -> 9
Enfoque: La idea es usar hashing para precalcular y almacenar los Nodes de Fibonacci hasta el valor máximo en la lista Vinculada, para que la verificación sea fácil y eficiente (en tiempo O(1)).
- Recorra toda la lista de enlaces individuales y obtenga el valor máximo en la lista.
- Ahora, cree una tabla hash que contenga todos los Nodes de Fibonacci menores o iguales al valor máximo en la lista de enlaces individuales.
Después de realizar el cálculo previo anterior, podemos comprobar si un número es un Fibonacci o no en tiempo constante. Por lo tanto, para realizar las operaciones anteriores, se utiliza el siguiente enfoque:
- Imprima los Nodes de Fibonacci: recorra la lista enlazada y verifique si el número es un valor de Fibonacci o no. Si es así, imprímelo.
- Cuente el número de Nodes de Fibonacci: para contar el número de Nodes de Fibonacci en la lista vinculada, recorremos la lista vinculada y verificamos si el número es un valor de Fibonacci o no.
- Encuentre los Nodes mínimo y máximo de Fibonacci: recorra la lista vinculada y verifique si el valor en un Node es un Fibonacci o no. En caso afirmativo:
- Si el valor del Node actual es mayor que max , entonces asigne el valor del Node actual a max.
- Si el valor del Node actual es menor que min , entonces asigne el valor del Node actual a min.
- Elimine los Nodes de Fibonacci: para eliminar los valores de Fibonacci, recorra la lista vinculada y, si los datos son de Fibonacci, elimine el Node que contiene los datos utilizando este enfoque .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to perform the
// operations on Fibonacci nodes
// of a Singly Linked list
#include <bits/stdc++.h>
using namespace std;
set<int> hashmap;
// Node of the singly linked list
struct Node {
int data;
Node* next;
};
// Function to insert a node at the beginning
// of the singly Linked List
void push(Node** head_ref, int new_data)
{
// Allocate a new node
Node* new_node = new Node;
// Insert the data
new_node->data = new_data;
new_node->next = (*head_ref);
// Move the head to point the new node
(*head_ref) = new_node;
}
// Function to delete a node in a SLL
// head_ref --> pointer to head node pointer.
// del --> pointer to node to be deleted
void deleteNode(Node** head_ref, Node* del)
{
// Base case
struct Node* temp = *head_ref;
if (*head_ref == NULL || del == NULL)
return;
// If the node to be deleted is
// the head node
if (*head_ref == del){
*head_ref = del->next;
return;
}
// Traverse list till not found
// delete node
while (temp->next != del) {
temp = temp->next;
}
// Copy address of node
temp->next = del->next;
return;
}
// Function that returns the largest element
// from the linked list.
int largestElement(struct Node* head_ref)
{
// Declare a max variable and
// initialize it with INT_MIN value.
// INT_MIN is integer type and
// its value is -32767 or less.
int max = INT_MIN;
Node* head = head_ref;
// Loop to iterate the linked list
while (head != NULL) {
// If max is less than head->data then
// assign value of head->data to max
// otherwise node point to next node.
if (max < head->data)
max = head->data;
head = head->next;
}
return max;
}
// Function to create a hash table
// to check Fibonacci nodes
void createHash(int maxElement)
{
// Insert the first two
// elements in the hash
int prev = 0, curr = 1;
hashmap.insert(prev);
hashmap.insert(curr);
// Add the elements until the max element
// by using the previous two numbers
while (curr <= maxElement) {
int temp = curr + prev;
hashmap.insert(temp);
prev = curr;
curr = temp;
}
}
// Function to print the Fibonacci
// nodes in a linked list
int printFibonacci(Node** head_ref)
{
int count = 0;
Node* ptr = *head_ref;
cout << "Fibonacci nodes = ";
while (ptr != NULL) {
// If current node is Fibonacci
if (hashmap.find(ptr->data)
!= hashmap.end()) {
// Update count
cout << ptr->data << " ";
}
ptr = ptr->next;
}
cout << endl;
return 0;
}
// Function to find the count of Fibonacci
// nodes in a linked list
int countFibonacci(Node** head_ref)
{
int count = 0;
Node* ptr = *head_ref;
while (ptr != NULL) {
// If current node is Fibonacci
if (hashmap.find(ptr->data)
!= hashmap.end()) {
// Update count
count++;
}
ptr = ptr->next;
}
return count;
}
// Function to find maximum and minimum
// fibonacci nodes in a linked list
void minmaxFibonacciNodes(Node** head_ref)
{
// Find the largest node value
// in Singly Linked List
int maxEle = largestElement(*head_ref);
// Creating a set containing
// all the Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
// set<int> hash;
// createHash(hash, maxEle);
int minimum = INT_MAX;
int maximum = INT_MIN;
Node* ptr = *head_ref;
while (ptr != NULL) {
// If current node is fibonacci
if (hashmap.find(ptr->data)
!= hashmap.end()) {
// Update minimum
minimum
= min(minimum, ptr->data);
// Update maximum
maximum
= max(maximum, ptr->data);
}
ptr = ptr->next;
}
cout << "Minimum Fibonacci node: "
<< minimum << endl;
cout << "Maximum Fibonacci node: "
<< maximum << endl;
}
// Function to delete all the
// fibonacci nodes from the
// singly linked list
void deleteFibonacciNodes(Node** head_ref)
{
Node* ptr = *head_ref;
Node* next;
// Iterating through the linked list
while (ptr != NULL) {
next = ptr->next;
// If the node's data is fibonacci,
// delete node 'ptr'
if (hashmap.find(ptr->data) != hashmap.end())
deleteNode(head_ref, ptr);
ptr = next;
}
}
// Function to print nodes in a
// given singly linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
void operations(struct Node* head)
{
// Find the largest node value
// in Singly Linked List
int maxEle = largestElement(head);
// Creating a set containing
// all Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
createHash(maxEle);
// Print all Fibonacci nodes
printFibonacci(&head);
// Count of Fibonacci nodes
cout << "Count of Fibonacci nodes = "
<< countFibonacci(&head) << endl;
// Minimum and maximum Fibonacci nodes
minmaxFibonacciNodes(&head);
// Delete Fibonacci nodes
deleteFibonacciNodes(&head);
cout << "List after deletion: ";
printList(head);
}
// Driver program
int main()
{
// Start with the empty list
Node* head = NULL;
// Create the linked list
// 15 -> 16 -> 8 -> 6 -> 13
push(&head, 13);
push(&head, 6);
push(&head, 8);
push(&head, 16);
push(&head, 8);
operations(head);
return 0;
}
Java
// Java implementation to perform the
// operations on Fibonacci nodes
// of a Singly Linked list
import java.util.*;
class GFG{
static HashSet<Integer> hashmap = new HashSet<Integer>();
// Node of the singly linked list
static class Node {
int data;
Node next;
};
// Function to insert a node at the beginning
// of the singly Linked List
static Node push(Node head_ref, int new_data)
{
// Allocate a new node
Node new_node = new Node();
// Insert the data
new_node.data = new_data;
new_node.next = head_ref;
// Move the head to point the new node
head_ref = new_node;
return head_ref;
}
// Function to delete a node in a SLL
// head_ref -. pointer to head node pointer.
// del -. pointer to node to be deleted
static Node deleteNode(Node head_ref, Node del)
{
// Base case
Node temp = head_ref;
if (head_ref == null || del == null)
return null;
// If the node to be deleted is
// the head node
if (head_ref == del)
head_ref = del.next;
// Traverse list till not found
// delete node
while (temp.next != del) {
temp = temp.next;
}
// Copy address of node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return head_ref;
}
// Function that returns the largest element
// from the linked list.
static int largestElement(Node head_ref)
{
// Declare a max variable and
// initialize it with Integer.MIN_VALUE value.
// Integer.MIN_VALUE is integer type and
// its value is -32767 or less.
int max = Integer.MIN_VALUE;
Node head = head_ref;
// Loop to iterate the linked list
while (head != null) {
// If max is less than head.data then
// assign value of head.data to max
// otherwise node point to next node.
if (max < head.data)
max = head.data;
head = head.next;
}
return max;
}
// Function to create a hash table
// to check Fibonacci nodes
static void createHash(int maxElement)
{
// Insert the first two
// elements in the hash
int prev = 0, curr = 1;
hashmap.add(prev);
hashmap.add(curr);
// Add the elements until the max element
// by using the previous two numbers
while (curr <= maxElement) {
int temp = curr + prev;
hashmap.add(temp);
prev = curr;
curr = temp;
}
}
// Function to print the Fibonacci
// nodes in a linked list
static int printFibonacci(Node head_ref)
{
int count = 0;
Node ptr = head_ref;
System.out.print("Fibonacci nodes = ");
while (ptr != null) {
// If current node is Fibonacci
if (hashmap.contains(ptr.data)) {
// Update count
System.out.print(ptr.data+ " ");
}
ptr = ptr.next;
}
System.out.println();
return 0;
}
// Function to find the count of Fibonacci
// nodes in a linked list
static int countFibonacci(Node head_ref)
{
int count = 0;
Node ptr = head_ref;
while (ptr != null) {
// If current node is Fibonacci
if (hashmap.contains(ptr.data)) {
// Update count
count++;
}
ptr = ptr.next;
}
return count;
}
// Function to find maximum and minimum
// fibonacci nodes in a linked list
static void minmaxFibonacciNodes(Node head_ref)
{
// Find the largest node value
// in Singly Linked List
int maxEle = largestElement(head_ref);
// Creating a set containing
// all the Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
// HashSet<Integer> hash;
// createHash(hash, maxEle);
int minimum = Integer.MAX_VALUE;
int maximum = Integer.MIN_VALUE;
Node ptr = head_ref;
while (ptr != null) {
// If current node is fibonacci
if (hashmap.contains(ptr.data)) {
// Update minimum
minimum
= Math.min(minimum, ptr.data);
// Update maximum
maximum
= Math.max(maximum, ptr.data);
}
ptr = ptr.next;
}
System.out.print("Minimum Fibonacci node: "
+ minimum +"\n");
System.out.print("Maximum Fibonacci node: "
+ maximum +"\n");
}
// Function to delete all the
// fibonacci nodes from the
// singly linked list
static Node deleteFibonacciNodes(Node head_ref)
{
Node ptr = head_ref;
Node next;
// Iterating through the linked list
while (ptr != null) {
next = ptr.next;
// If the node's data is fibonacci,
// delete node 'ptr'
if (hashmap.contains(ptr.data))
deleteNode(head_ref, ptr);
ptr = next;
}
return head_ref;
}
// Function to print nodes in a
// given singly linked list
static void printList(Node head)
{
while (head != null) {
System.out.print(head.data+ " ");
head = head.next;
}
}
static void operations(Node head)
{
// Find the largest node value
// in Singly Linked List
int maxEle = largestElement(head);
// Creating a set containing
// all Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
createHash(maxEle);
// Print all Fibonacci nodes
printFibonacci(head);
// Count of Fibonacci nodes
System.out.print("Count of Fibonacci nodes = "
+ countFibonacci(head) +"\n");
// Minimum and maximum Fibonacci nodes
minmaxFibonacciNodes(head);
// Delete Fibonacci nodes
head = deleteFibonacciNodes(head);
System.out.print("List after deletion: ");
printList(head);
}
// Driver program
public static void main(String[] args)
{
// Start with the empty list
Node head = null;
// Create the linked list
// 15.16.8.6.13
head = push(head, 13);
head = push(head, 6);
head = push(head, 8);
head = push(head, 16);
head = push(head, 15);
operations(head);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to perform the
# operations on Fibonacci nodes
# of a Singly Linked list
hashmap = set()
# Node of the singly linked list
class Node:
def __init(self):
self.data = 0
self.next = None
# Function to add a node at the beginning
# of the singly Linked List
def push(head_ref, new_data):
# Allocate a new node
new_node = Node()
# Insert the data
new_node.data = new_data;
new_node.next = (head_ref);
# Move the head to point the new node
(head_ref) = new_node;
return head_ref
# Function to delete a node in a SLL
# head_ref -. pointer to head node pointer.
# delt -. pointer to node to be deleted
def deleteNode(head_ref, delt):
# Base case
temp = head_ref;
if (head_ref == None or delt == None):
return;
# If the node to be deleted is
# the head node
if (head_ref == delt):
head_ref = delt.next;
# Traverse list till not found
# delete node
while (temp.next != delt):
temp = temp.next;
# Copy address of node
temp.next = delt.next;
# Finally, free the memory
# occupied by delt
del(delt);
return;
# Function that returns the largest element
# from the linked list.
def largestElement(head_ref):
# Declare a max variable and
# initialize it with INT_MIN value.
# INT_MIN is integer type and
# its value is -32767 or less.
max = -10000000
head = head_ref;
# Loop to iterate the linked list
while (head != None):
# If max is less than head.data then
# assign value of head.data to max
# otherwise node point to next node.
if (max < head.data):
max = head.data;
head = head.next;
return max;
# Function to create a hash table
# to check Fibonacci nodes
def createHash(maxElement):
# Insert the first two
# elements in the hash
prev = 0
curr = 1;
hashmap.add(prev);
hashmap.add(curr);
# Add the elements until the max element
# by using the previous two numbers
while (curr <= maxElement):
temp = curr + prev;
hashmap.add(temp);
prev = curr;
curr = temp;
# Function to print the Fibonacci
# nodes in a linked list
def printFibonacci(head_ref):
count = 0;
ptr = head_ref
print("Fibonacci nodes = ",end='')
while (ptr != None):
# If current node is Fibonacci
if (ptr.data in hashmap):
# Update count
print(ptr.data, end=' ')
ptr = ptr.next;
print()
return 0;
# Function to find the count of Fibonacci
# nodes in a linked list
def countFibonacci(head_ref):
count = 0;
ptr = head_ref;
while (ptr != None):
# If current node is Fibonacci
if (ptr.data in hashmap):
# Update count
count += 1
ptr = ptr.next;
return count;
# Function to find maximum and minimum
# fibonacci nodes in a linked list
def minmaxFibonacciNodes(head_ref):
# Find the largest node value
# in Singly Linked List
maxEle = largestElement(head_ref);
# Creating a set containing
# all the Fibonacci nodes
# upto the maximum data value
# in the Singly Linked List
# set<int> hash;
# createHash(hash, maxEle);
minimum = 100000000
maximum = -100000000
ptr = head_ref;
while (ptr != None):
# If current node is fibonacci
if (ptr.data in hashmap):
# Update minimum
minimum = min(minimum, ptr.data);
# Update maximum
maximum = max(maximum, ptr.data);
ptr = ptr.next;
print("Minimum Fibonacci node: "+str(minimum))
print("Maximum Fibonacci node: "+str(maximum))
# Function to delete all the
# fibonacci nodes from the
# singly linked list
def deleteFibonacciNodes(head_ref):
ptr = head_ref;
next = None
# Iterating through the linked list
while (ptr != None):
next = ptr.next;
# If the node's data is fibonacci,
# delete node 'ptr'
if (ptr.data in hashmap):
deleteNode(head_ref, ptr);
ptr = next;
# Function to print nodes in a
# given singly linked list
def printList(head):
while (head != None):
print(head.data, end = ' ')
head = head.next;
def operations(head):
# Find the largest node value
# in Singly Linked List
maxEle = largestElement(head);
# Creating a set containing
# all Fibonacci nodes
# upto the maximum data value
# in the Singly Linked List
createHash(maxEle);
# Print all Fibonacci nodes
printFibonacci(head);
# Count of Fibonacci nodes
print("Count of Fibonacci nodes = " + str(countFibonacci(head)))
# Minimum and maximum Fibonacci nodes
minmaxFibonacciNodes(head);
# Delete Fibonacci nodes
deleteFibonacciNodes(head);
print("List after deletion: ", end='')
printList(head);
# Driver program
if __name__=='__main__':
# Start with the empty list
head = None;
# Create the linked list
# 15 . 16 . 8 . 6 . 13
head = push(head, 13);
head = push(head, 6);
head = push(head, 8);
head = push(head, 16);
head = push(head, 15);
operations(head);
# This code is contributed by rutvik_56
C#
// C# implementation to perform the
// operations on Fibonacci nodes
// of a Singly Linked list
using System;
using System.Collections.Generic;
class GFG{
static HashSet<int> hashmap = new HashSet<int>();
// Node of the singly linked list
class Node {
public int data;
public Node next;
};
// Function to insert a node at the beginning
// of the singly Linked List
static Node push(Node head_ref, int new_data)
{
// Allocate a new node
Node new_node = new Node();
// Insert the data
new_node.data = new_data;
new_node.next = head_ref;
// Move the head to point the new node
head_ref = new_node;
return head_ref;
}
// Function to delete a node in a SLL
// head_ref -. pointer to head node pointer.
// del -. pointer to node to be deleted
static Node deleteNode(Node head_ref, Node del)
{
// Base case
Node temp = head_ref;
if (head_ref == null || del == null)
return null;
// If the node to be deleted is
// the head node
if (head_ref == del)
head_ref = del.next;
// Traverse list till not found
// delete node
while (temp.next != del) {
temp = temp.next;
}
// Copy address of node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return head_ref;
}
// Function that returns the largest element
// from the linked list.
static int largestElement(Node head_ref)
{
// Declare a max variable and
// initialize it with int.MinValue value.
// int.MinValue is integer type and
// its value is -32767 or less.
int max = int.MinValue;
Node head = head_ref;
// Loop to iterate the linked list
while (head != null) {
// If max is less than head.data then
// assign value of head.data to max
// otherwise node point to next node.
if (max < head.data)
max = head.data;
head = head.next;
}
return max;
}
// Function to create a hash table
// to check Fibonacci nodes
static void createHash(int maxElement)
{
// Insert the first two
// elements in the hash
int prev = 0, curr = 1;
hashmap.Add(prev);
hashmap.Add(curr);
// Add the elements until the max element
// by using the previous two numbers
while (curr <= maxElement) {
int temp = curr + prev;
hashmap.Add(temp);
prev = curr;
curr = temp;
}
}
// Function to print the Fibonacci
// nodes in a linked list
static int printFibonacci(Node head_ref)
{
Node ptr = head_ref;
Console.Write("Fibonacci nodes = ");
while (ptr != null) {
// If current node is Fibonacci
if (hashmap.Contains(ptr.data)) {
// Update count
Console.Write(ptr.data+ " ");
}
ptr = ptr.next;
}
Console.WriteLine();
return 0;
}
// Function to find the count of Fibonacci
// nodes in a linked list
static int countFibonacci(Node head_ref)
{
int count = 0;
Node ptr = head_ref;
while (ptr != null) {
// If current node is Fibonacci
if (hashmap.Contains(ptr.data)) {
// Update count
count++;
}
ptr = ptr.next;
}
return count;
}
// Function to find maximum and minimum
// fibonacci nodes in a linked list
static void minmaxFibonacciNodes(Node head_ref)
{
// Find the largest node value
// in Singly Linked List
int maxEle = largestElement(head_ref);
// Creating a set containing
// all the Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
// HashSet<int> hash;
// createHash(hash, maxEle);
int minimum = int.MaxValue;
int maximum = int.MinValue;
Node ptr = head_ref;
while (ptr != null) {
// If current node is fibonacci
if (hashmap.Contains(ptr.data)) {
// Update minimum
minimum
= Math.Min(minimum, ptr.data);
// Update maximum
maximum
= Math.Max(maximum, ptr.data);
}
ptr = ptr.next;
}
Console.Write("Minimum Fibonacci node: "
+ minimum +"\n");
Console.Write("Maximum Fibonacci node: "
+ maximum +"\n");
}
// Function to delete all the
// fibonacci nodes from the
// singly linked list
static Node deleteFibonacciNodes(Node head_ref)
{
Node ptr = head_ref;
Node next;
// Iterating through the linked list
while (ptr != null) {
next = ptr.next;
// If the node's data is fibonacci,
// delete node 'ptr'
if (hashmap.Contains(ptr.data))
deleteNode(head_ref, ptr);
ptr = next;
}
return head_ref;
}
// Function to print nodes in a
// given singly linked list
static void printList(Node head)
{
while (head != null) {
Console.Write(head.data+ " ");
head = head.next;
}
}
static void operations(Node head)
{
// Find the largest node value
// in Singly Linked List
int maxEle = largestElement(head);
// Creating a set containing
// all Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
createHash(maxEle);
// Print all Fibonacci nodes
printFibonacci(head);
// Count of Fibonacci nodes
Console.Write("Count of Fibonacci nodes = "
+ countFibonacci(head) +"\n");
// Minimum and maximum Fibonacci nodes
minmaxFibonacciNodes(head);
// Delete Fibonacci nodes
head = deleteFibonacciNodes(head);
Console.Write("List after deletion: ");
printList(head);
}
// Driver program
public static void Main(String[] args)
{
// Start with the empty list
Node head = null;
// Create the linked list
// 15.16.8.6.13
head = push(head, 13);
head = push(head, 6);
head = push(head, 8);
head = push(head, 16);
head = push(head, 15);
operations(head);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript implementation to perform the
// operations on Fibonacci nodes
// of a Singly Linked list
var hashmap = new Set();
// Node of the singly linked list
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to insert a node at the beginning
// of the singly Linked List
function push(head_ref , new_data) {
// Allocate a new node
var new_node = new Node();
// Insert the data
new_node.data = new_data;
new_node.next = head_ref;
// Move the head to point the new node
head_ref = new_node;
return head_ref;
}
// Function to delete a node in a SLL
// head_ref -. pointer to head node pointer.
// del -. pointer to node to be deleted
function deleteNode(head_ref, del) {
// Base case
var temp = head_ref;
if (head_ref == null || del == null)
return null;
// If the node to be deleted is
// the head node
if (head_ref == del)
head_ref = del.next;
// Traverse list till not found
// delete node
while (temp.next != del) {
temp = temp.next;
}
// Copy address of node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return head_ref;
}
// Function that returns the largest element
// from the linked list.
function largestElement(head_ref) {
// Declare a max variable and
// initialize it with Number.MIN_VALUE value.
// Number.MIN_VALUE is integer type and
// its value is -32767 or less.
var max = Number.MIN_VALUE;
var head = head_ref;
// Loop to iterate the linked list
while (head != null) {
// If max is less than head.data then
// assign value of head.data to max
// otherwise node point to next node.
if (max < head.data)
max = head.data;
head = head.next;
}
return max;
}
// Function to create a hash table
// to check Fibonacci nodes
function createHash(maxElement) {
// Insert the first two
// elements in the hash
var prev = 0, curr = 1;
hashmap.add(prev);
hashmap.add(curr);
// Add the elements until the max element
// by using the previous two numbers
while (curr <= maxElement) {
var temp = curr + prev;
hashmap.add(temp);
prev = curr;
curr = temp;
}
}
// Function to print the Fibonacci
// nodes in a linked list
function printFibonacci(head_ref) {
var count = 0;
var ptr = head_ref;
document.write("Fibonacci nodes = ");
while (ptr != null) {
// If current node is Fibonacci
if (hashmap.has(ptr.data)) {
// Update count
document.write(ptr.data + " ");
}
ptr = ptr.next;
}
document.write("<br/>");
return 0;
}
// Function to find the count of Fibonacci
// nodes in a linked list
function countFibonacci(head_ref) {
var count = 0;
var ptr = head_ref;
while (ptr != null) {
// If current node is Fibonacci
if (hashmap.has(ptr.data)) {
// Update count
count++;
}
ptr = ptr.next;
}
return count;
}
// Function to find maximum and minimum
// fibonacci nodes in a linked list
function minmaxFibonacciNodes(head_ref) {
// Find the largest node value
// in Singly Linked List
var maxEle = largestElement(head_ref);
// Creating a set containing
// all the Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
// HashSet<Integer> hash;
// createHash(hash, maxEle);
var minimum = Number.MAX_VALUE;
var maximum = Number.MIN_VALUE;
var ptr = head_ref;
while (ptr != null) {
// If current node is fibonacci
if (hashmap.has(ptr.data)) {
// Update minimum
minimum = Math.min(minimum, ptr.data);
// Update maximum
maximum = Math.max(maximum, ptr.data);
}
ptr = ptr.next;
}
document.write("Minimum Fibonacci node: " + minimum + "<br/>");
document.write("Maximum Fibonacci node: " + maximum + "<br/>");
}
// Function to delete all the
// fibonacci nodes from the
// singly linked list
function deleteFibonacciNodes(head_ref) {
var ptr = head_ref;
var next;
// Iterating through the linked list
while (ptr != null) {
next = ptr.next;
// If the node's data is fibonacci,
// delete node 'ptr'
if (hashmap.has(ptr.data))
deleteNode(head_ref, ptr);
ptr = next;
}
return head_ref;
}
// Function to print nodes in a
// given singly linked list
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
function operations(head) {
// Find the largest node value
// in Singly Linked List
var maxEle = largestElement(head);
// Creating a set containing
// all Fibonacci nodes
// upto the maximum data value
// in the Singly Linked List
createHash(maxEle);
// Print all Fibonacci nodes
printFibonacci(head);
// Count of Fibonacci nodes
document.write("Count of Fibonacci nodes = " + countFibonacci(head) + "<br/>");
// Minimum and maximum Fibonacci nodes
minmaxFibonacciNodes(head);
// Delete Fibonacci nodes
head = deleteFibonacciNodes(head);
document.write("List after deletion: ");
printList(head);
}
// Driver program
// Start with the empty list
var head = null;
// Create the linked list
// 15.16.8.6.13
head = push(head, 13);
head = push(head, 6);
head = push(head, 8);
head = push(head, 16);
head = push(head, 15);
operations(head);
// This code contributed by gauravrajput1
</script>
Producción
Fibonacci nodes = 8 8 13 Count of Fibonacci nodes = 3 Minimum Fibonacci node: 8 Maximum Fibonacci node: 13 List after deletion: 16 6
Complejidad de tiempo: O(N), donde N es el número de Nodes en la lista enlazada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA