Dada una lista circular enlazada individualmente que contiene N Nodes, la tarea es eliminar todos los Nodes de la lista que contiene valores de datos de Fibonacci .
Ejemplos:
Entrada: CLL = 9 -> 11 -> 34 -> 6 -> 13 -> 20
Salida: 9 -> 11 -> 6 -> 20
Explicación:
La lista contiene 2 valores de datos de fibonacci 32 y 13.
Por lo tanto, los Nodes que contienen estos datos han sido eliminados
Entrada: 5 -> 11 -> 16 -> 21 -> 17 -> 10
Salida: 11 -> 16 -> 17 -> 10
Explicación:
La lista contiene 2 valores de datos de fibonacci 5 y 21.
Por lo tanto, los Nodes que contienen estos datos han sido eliminados
Enfoque: la idea es usar hashing para precalcular y almacenar los números de Fibonacci , y luego verificar si un Node contiene un valor de Fibonacci en tiempo O (1).
- Recorra toda la lista circular enlazada individualmente y obtenga el valor máximo en la lista.
- Ahora, para verificar los números de Fibonacci, cree una tabla hash que contenga todos los números de Fibonacci menores o iguales al valor máximo en la lista circular de enlaces simples.
- Finalmente, recorra los Nodes de la lista circular enlazada individualmente uno por uno y verifique si el Node contiene números de Fibonacci como su valor de datos. Elimina los Nodes que tienen valor de Fibonacci.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to delete all the
// Fibonacci nodes from the
// circular singly linked list
#include <bits/stdc++.h>
using namespace std;
// Structure for a node
struct Node {
int data;
struct Node* next;
};
// Function to insert a node at the beginning
// of a Circular linked list
void push(struct Node** head_ref, int data)
{
// Create a new node and make head as next
// of it.
struct Node* ptr1
= (struct Node*)malloc(
sizeof(struct Node));
struct Node* temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
// If linked list is not NULL then
// set the next of last node
if (*head_ref != NULL) {
// Find the node before head
// and update next of it.
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
// Point for the first node
ptr1->next = ptr1;
*head_ref = ptr1;
}
// Delete the node from a Circular Linked list
void deleteNode(Node* head_ref, Node* del)
{
struct Node* temp = head_ref;
// If node to be deleted is 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 the address of the node
temp->next = del->next;
// Finally, free the memory
// occupied by del
free(del);
return;
}
// Function to find the maximum
// node of the circular linked list
int largestElement(struct Node* head_ref)
{
// Pointer for traversing
struct Node* current;
// Initialize head to the current pointer
current = head_ref;
// Initialize min int value to max
int maxEle = INT_MIN;
// While the last node is not reached
do {
// If current node data is
// greater for max then replace it
if (current->data > maxEle) {
maxEle = current->data;
}
current = current->next;
} while (current != head_ref);
return maxEle;
}
// Function to create hash table to
// check Fibonacci numbers
void createHash(set<int>& hash,
int maxElement)
{
int prev = 0, curr = 1;
// Adding the first two elements
// to the hash
hash.insert(prev);
hash.insert(curr);
// Inserting the Fibonacci numbers
// into the hash
while (curr <= maxElement) {
int temp = curr + prev;
hash.insert(temp);
prev = curr;
curr = temp;
}
}
// Function to delete all the Fibonacci nodes
// from the singly circular linked list
void deleteFibonacciNodes(Node* head)
{
// Find the largest node value
// in Circular Linked List
int maxEle = largestElement(head);
// Creating a hash containing
// all the Fibonacci numbers
// upto the maximum data value
// in the circular linked list
set<int> hash;
createHash(hash, maxEle);
struct Node* ptr = head;
struct Node* next;
// Traverse the list till the end
do {
// If the node's data is Fibonacci,
// delete node 'ptr'
if (hash.find(ptr->data)
!= hash.end())
deleteNode(head, ptr);
// Point to the next node
next = ptr->next;
ptr = next;
} while (ptr != head);
}
// Function to print nodes in a
// given Circular linked list
void printList(struct Node* head)
{
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
}
// Driver code
int main()
{
// Initialize lists as empty
struct Node* head = NULL;
// Created linked list will be
// 9->11->34->6->13->20
push(&head, 20);
push(&head, 13);
push(&head, 6);
push(&head, 34);
push(&head, 11);
push(&head, 9);
deleteFibonacciNodes(head);
printList(head);
return 0;
}
Java
// Java program to delete all the
// Fibonacci nodes from the
// circular singly linked list
import java.util.*;
class GFG{
// Structure for a node
static class Node {
int data;
Node next;
};
// Function to insert a node at the beginning
// of a Circular linked list
static Node push(Node head_ref, int data)
{
// Create a new node and make head as next
// of it.
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null) {
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Delete the node from a Circular Linked list
static void deleteNode(Node head_ref, Node del)
{
Node temp = head_ref;
// If node to be deleted is 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 the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return;
}
// Function to find the maximum
// node of the circular linked list
static int largestElement(Node head_ref)
{
// Pointer for traversing
Node current;
// Initialize head to the current pointer
current = head_ref;
// Initialize min int value to max
int maxEle = Integer.MIN_VALUE;
// While the last node is not reached
do {
// If current node data is
// greater for max then replace it
if (current.data > maxEle) {
maxEle = current.data;
}
current = current.next;
} while (current != head_ref);
return maxEle;
}
// Function to create hash table to
// check Fibonacci numbers
static void createHash(HashSet<Integer> hash,
int maxElement)
{
int prev = 0, curr = 1;
// Adding the first two elements
// to the hash
hash.add(prev);
hash.add(curr);
// Inserting the Fibonacci numbers
// into the hash
while (curr <= maxElement) {
int temp = curr + prev;
hash.add(temp);
prev = curr;
curr = temp;
}
}
// Function to delete all the Fibonacci nodes
// from the singly circular linked list
static void deleteFibonacciNodes(Node head)
{
// Find the largest node value
// in Circular Linked List
int maxEle = largestElement(head);
// Creating a hash containing
// all the Fibonacci numbers
// upto the maximum data value
// in the circular linked list
HashSet<Integer> hash = new HashSet<Integer>();
createHash(hash, maxEle);
Node ptr = head;
Node next;
// Traverse the list till the end
do {
// If the node's data is Fibonacci,
// delete node 'ptr'
if (hash.contains(ptr.data))
deleteNode(head, ptr);
// Point to the next node
next = ptr.next;
ptr = next;
} while (ptr != head);
}
// Function to print nodes in a
// given Circular linked list
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
System.out.printf("%d ", temp.data);
temp = temp.next;
} while (temp != head);
}
}
// Driver code
public static void main(String[] args)
{
// Initialize lists as empty
Node head = null;
// Created linked list will be
// 9.11.34.6.13.20
head = push(head, 20);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 11);
head = push(head, 9);
deleteFibonacciNodes(head);
printList(head);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to delete all the # Fibonacci nodes from the # circular singly linked list # Structure for a node class Node: def __init__(self): self.data = 0 self.next = None # Function to add a node at the beginning # of a Circular linked list def push(head_ref, data): # Create a new node and make head as next # of it. ptr1 = Node() temp = head_ref; ptr1.data = data; ptr1.next = head_ref; # If linked list is not None then # set the next of last node if (head_ref != None): # Find the node before head # and update next of it. while (temp.next != head_ref): temp = temp.next; temp.next = ptr1; else: # Point for the first node ptr1.next = ptr1; head_ref = ptr1; return head_ref # Delete the node from a Circular Linked list def deleteNode( head_ref, delt): temp = head_ref; # If node to be deleted is 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 the address of the node temp.next = delt.next; # Finally, free the memory # occupied by delt del(delt); return; # Function to find the maximum # node of the circular linked list def largestElement( head_ref): # Pointer for traversing current = None # Initialize head to the current pointer current = head_ref; # Initialize min value to max maxEle = -10000000 # While the last node is not reached while(True): # If current node data is # greater for max then replace it if (current.data > maxEle): maxEle = current.data; current = current.next; if(current == head_ref): break return maxEle; # Function to create hashmap table to # check Fibonacci numbers def createHash(hashmap, maxElement): prev = 0 curr = 1; # Adding the first two elements # to the hashmap hashmap.add(prev); hashmap.add(curr); # Inserting the Fibonacci numbers # into the hashmap while (curr <= maxElement): temp = curr + prev; hashmap.add(temp); prev = curr; curr = temp; # Function to delete all the Fibonacci nodes # from the singly circular linked list def deleteFibonacciNodes( head): # Find the largest node value # in Circular Linked List maxEle = largestElement(head); # Creating a hashmap containing # all the Fibonacci numbers # upto the maximum data value # in the circular linked list hashmap = set() createHash(hashmap, maxEle); ptr = head; next = None # Traverse the list till the end while(True): # If the node's data is Fibonacci, # delete node 'ptr' if (ptr.data in hashmap): deleteNode(head, ptr); # Point to the next node next = ptr.next; ptr = next; if(ptr == head): break # Function to print nodes in a # given Circular linked list def printList( head): temp = head; if (head != None): while(True): print(temp.data, end = ' ') temp = temp.next if(temp == head): break # Driver code if __name__=='__main__': # Initialize lists as empty head = None; # Created linked list will be # 9.11.34.6.13.20 head = push(head, 20); head = push(head, 13); head = push(head, 6); head = push(head, 34); head = push(head, 11); head = push(head, 9); deleteFibonacciNodes(head); printList(head); # This code is contributed by rutvik_56
C#
// C# program to delete all the
// Fibonacci nodes from the
// circular singly linked list
using System;
using System.Collections.Generic;
class GFG{
// Structure for a node
class Node {
public int data;
public Node next;
};
// Function to insert a node at the beginning
// of a Circular linked list
static Node push(Node head_ref, int data)
{
// Create a new node and make head as next
// of it.
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null) {
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Delete the node from a Circular Linked list
static void deleteNode(Node head_ref, Node del)
{
Node temp = head_ref;
// If node to be deleted is 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 the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return;
}
// Function to find the maximum
// node of the circular linked list
static int largestElement(Node head_ref)
{
// Pointer for traversing
Node current;
// Initialize head to the current pointer
current = head_ref;
// Initialize min int value to max
int maxEle = int.MinValue;
// While the last node is not reached
do {
// If current node data is
// greater for max then replace it
if (current.data > maxEle) {
maxEle = current.data;
}
current = current.next;
} while (current != head_ref);
return maxEle;
}
// Function to create hash table to
// check Fibonacci numbers
static void createHash(HashSet<int> hash,
int maxElement)
{
int prev = 0, curr = 1;
// Adding the first two elements
// to the hash
hash.Add(prev);
hash.Add(curr);
// Inserting the Fibonacci numbers
// into the hash
while (curr <= maxElement) {
int temp = curr + prev;
hash.Add(temp);
prev = curr;
curr = temp;
}
}
// Function to delete all the Fibonacci nodes
// from the singly circular linked list
static void deleteFibonacciNodes(Node head)
{
// Find the largest node value
// in Circular Linked List
int maxEle = largestElement(head);
// Creating a hash containing
// all the Fibonacci numbers
// upto the maximum data value
// in the circular linked list
HashSet<int> hash = new HashSet<int>();
createHash(hash, maxEle);
Node ptr = head;
Node next;
// Traverse the list till the end
do {
// If the node's data is Fibonacci,
// delete node 'ptr'
if (hash.Contains(ptr.data))
deleteNode(head, ptr);
// Point to the next node
next = ptr.next;
ptr = next;
} while (ptr != head);
}
// Function to print nodes in a
// given Circular linked list
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
Console.Write("{0} ", temp.data);
temp = temp.next;
} while (temp != head);
}
}
// Driver code
public static void Main(String[] args)
{
// Initialize lists as empty
Node head = null;
// Created linked list will be
// 9.11.34.6.13.20
head = push(head, 20);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 11);
head = push(head, 9);
deleteFibonacciNodes(head);
printList(head);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript program to delete all the
// Fibonacci nodes from the
// circular singly linked list
// Structure for a node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to insert a node at the beginning
// of a Circular linked list
function push(head_ref , data) {
// Create a new node and make head as next
// of it.
var ptr1 = new Node();
var temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null) {
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Delete the node from a Circular Linked list
function deleteNode(head_ref, del) {
var temp = head_ref;
// If node to be deleted is 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 the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return;
}
// Function to find the maximum
// node of the circular linked list
function largestElement(head_ref) {
// Pointer for traversing
var current;
// Initialize head to the current pointer
current = head_ref;
// Initialize min var value to max
var maxEle = Number.MIN_VALUE;
// While the last node is not reached
do {
// If current node data is
// greater for max then replace it
if (current.data > maxEle) {
maxEle = current.data;
}
current = current.next;
} while (current != head_ref);
return maxEle;
}
// Function to create hash table to
// check Fibonacci numbers
function createHash( hash , maxElement) {
var prev = 0, curr = 1;
// Adding the first two elements
// to the hash
hash.add(prev);
hash.add(curr);
// Inserting the Fibonacci numbers
// into the hash
while (curr <= maxElement) {
var temp = curr + prev;
hash.add(temp);
prev = curr;
curr = temp;
}
}
// Function to delete all the Fibonacci nodes
// from the singly circular linked list
function deleteFibonacciNodes(head) {
// Find the largest node value
// in Circular Linked List
var maxEle = largestElement(head);
// Creating a hash containing
// all the Fibonacci numbers
// upto the maximum data value
// in the circular linked list
var hash = new Set();
createHash(hash, maxEle);
var ptr = head;
var next;
// Traverse the list till the end
do {
// If the node's data is Fibonacci,
// delete node 'ptr'
if (hash.has(ptr.data))
deleteNode(head, ptr);
// Point to the next node
next = ptr.next;
ptr = next;
} while (ptr != head);
}
// Function to print nodes in a
// given Circular linked list
function printList(head) {
var temp = head;
if (head != null) {
do {
document.write(temp.data+" ");
temp = temp.next;
} while (temp != head);
}
}
// Driver code
// Initialize lists as empty
var head = null;
// Created linked list will be
// 9.11.34.6.13.20
head = push(head, 20);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 11);
head = push(head, 9);
deleteFibonacciNodes(head);
printList(head);
// This code contributed by aashish1995
</script>
Producción:
9 11 6 20
Complejidad de tiempo: O(n + log(maxElement)) (tabla hash de generación real de fibonacci no. hasta maxElement requerido O(log(maxElement)) tiempo + O(n) para atravesar LinkList que contiene el Node n)
Espacio auxiliar: O (log (maxElement)) (almacenamiento de números de fibonacci en hash)
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