Dada una lista doblemente enlazada que contiene N Nodes, la tarea es eliminar todos los Nodes de la lista que contiene números de Fibonacci .
Ejemplos:
Entrada: DLL = 15 <=> 16 <=> 8 <=> 7 <=> 13
Salida: 15 <=> 16 <=> 7
Explicación:
La lista enlazada contiene dos números de Fibonacci 8 y 13.
Por lo tanto, estos Nodes tienen sido borrado
Entrada: DLL = 5 <=> 3 <=> 4 <=> 2 <=> 9
Salida: 4 <=> 9
Explicación:
La lista enlazada contiene tres números de Fibonacci 5, 3 y 2.
Por lo tanto, estos Nodes se han eliminado .
Enfoque: La idea es usar hashing para almacenar y verificar los números de Fibonacci .
- Recorra toda la lista doblemente enlazada 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 vinculada.
- Finalmente, recorra los Nodes de la lista doblemente enlazada uno por uno y elimine los Nodes que contienen números de Fibonacci como su valor de datos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to delete all
// Fibonacci nodes from the
// doubly linked list
#include
using namespace std;
// Node of the doubly linked list
struct Node {
int data;
Node *prev, *next;
};
// Function to insert a node at the beginning
// of the Doubly Linked List
void push(Node** head_ref, int new_data)
{
// Allocate the node
Node* new_node
= (Node*)malloc(sizeof(struct Node));
// Insert the data
new_node->data = new_data;
// Since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// Link the old list off the new node
new_node->next = (*head_ref);
// Change the prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// Move the head to point to the new node
(*head_ref) = new_node;
}
// Function to find the largest
// nodes in the Doubly Linked List
int LargestInDLL(struct Node** head_ref)
{
struct Node *max, *temp;
// Initialize two-pointer temp
// and max on the head node
temp = max = *head_ref;
// Traverse the whole doubly linked list
while (temp != NULL) {
// If temp's data is greater than
// the max's data, then max = temp
// and return max->data
if (temp->data > max->data)
max = temp;
temp = temp->next;
}
return max->data;
}
// Function to create hash table to
// check Fibonacci numbers
void createHash(set& hash, int maxElement)
{
int prev = 0, curr = 1;
hash.insert(prev);
hash.insert(curr);
// Inserting the Fibonacci numbers
// until the maximum element in the
// Linked List
while (curr pointer to head node pointer.
// del --> pointer to node to be deleted
void deleteNode(Node** head_ref, Node* del)
{
// Base case
if (*head_ref == NULL || del == NULL)
return;
// If the node to be deleted is head node
if (*head_ref == del)
*head_ref = del->next;
// Change next only if node to be
// deleted is not the last node
if (del->next != NULL)
del->next->prev = del->prev;
// Change prev only if node to be
// deleted is not the first node
if (del->prev != NULL)
del->prev->next = del->next;
// Finally, free the memory
// occupied by del
free(del);
return;
}
// Function to delete all fibonacci nodes
// from the doubly linked list
void deleteFibonacciNodes(Node** head_ref)
{
// Find the largest node value
// in Doubly Linked List
int maxEle = LargestInDLL(head_ref);
// Creating a set containing
// all the fibonacci numbers
// upto the maximum data value
// in the Doubly Linked List
set hash;
createHash(hash, maxEle);
Node* ptr = *head_ref;
Node* next;
// Iterating through the linked list
while (ptr != NULL) {
next = ptr->next;
// If node's data is fibonacci,
// delete node 'ptr'
if (hash.find(ptr->data) != hash.end())
deleteNode(head_ref, ptr);
ptr = next;
}
}
// Function to print nodes in a
// given doubly linked list
void printList(Node* head)
{
while (head != NULL) {
cout <data <next;
}
}
// Driver program
int main()
{
Node* head = NULL;
// Create the doubly linked list
// 15 16 8 6 13
push(&head, 13);
push(&head, 6);
push(&head, 8);
push(&head, 16);
push(&head, 15);
cout << "Original List: ";
printList(head);
deleteFibonacciNodes(&head);
cout << "\nModified List: ";
printList(head);
}
Java
// Java implementation to delete all Fibonacci nodes from
// the doubly linked list
import java.io.*;
import java.util.*;
class GFG {
// Node of a doubly linked list
class Node {
int data;
Node next, prev;
}
Node head = null;
HashSet<Integer> hashset = new HashSet<Integer>();
// Function to add a node at the beginning of the doubly
// linked list.
public Node push(int new_data)
{
// Allocate the node
Node new_node = new Node();
// Insert the data
new_node.data = new_data;
// Since we are adding at the beginning, prev is
// always null
new_node.prev = null;
// Link the old list off the new node
new_node.next = head;
// change the prev of head node to new node
if (head != null) {
head.prev = new_node;
}
// move the head to point to the new node.
head = new_node;
return head;
}
// Function to find the largest nodes in the doubly
// linked list.
public int LargestInDLL()
{
// Initialize two pointer temp and max on to the
// head node.
Node max = head;
Node temp = head;
// Traverse the whole doubly linked list
while (temp != null) {
// If temp's data is greater than the max's
// data, then max = temp and return max.data
if (temp.data > max.data) {
max = temp;
}
temp = temp.next;
}
return max.data;
}
// Function to create hashset table to check Fibonacci
// numbers
public void createHash(int maxElement)
{
int prev = 0, curr = 1;
hashset.add(prev);
hashset.add(curr);
// Inserting the Fibonacci numbers until the maximum
// element in the Linked List.
while (curr <= maxElement) {
int temp = curr + prev;
hashset.add(temp);
prev = curr;
curr = temp;
}
}
// Function to delete a node in a Doubly linked list.
// delt -> pointer to node to be deleted.
public void deleteNode(Node delt)
{
// Base case
if (head == null || delt == null) {
return;
}
// If the node to be deleted is head node
if (head == delt) {
head = delt.next;
}
// Change next only if node to be delete is not the
// last node
if (delt.next != null) {
delt.next.prev = delt.prev;
}
// Change prev only if node to be deleted is not the
// first node
if (delt.prev != null) {
delt.prev.next = delt.next;
}
return;
}
// Function to delete all fibonacci nodes from the
// doubly linked list.
public void deleteFibonacciNodes()
{
// Find the largest node value in doubly linked
// list.
int maxEle = LargestInDLL();
createHash(maxEle);
Node ptr = head;
Node next = null;
// Iterating through the linked list
while (ptr != null) {
next = ptr.next;
// If node's data is fibonacci, delete node
// 'ptr'
if (hashset.contains(ptr.data)) {
deleteNode(ptr);
}
ptr = next;
}
}
// Function to print nodes in a given doubly linked
// list.
public void printList()
{
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args)
{
GFG l = new GFG();
// Create the doubly linked list.
// null<- 15 <-> 16 <-> 8 <-> 6 <-> 13 -> null
l.push(13);
l.push(6);
l.push(8);
l.push(16);
l.push(15);
System.out.print("Original List: ");
l.printList();
l.deleteFibonacciNodes();
System.out.print("Modilied List: ");
l.printList();
}
}
// This code is contributed by lokeshmvs21
Python3
# Python3 implementation to delete all
# Fibonacci nodes from the
# doubly linked list
# Node of the doubly linked list
class Node:
def __init__(self):
self.data = 0
self.next = None
self.prev = None
# Function to add a node at the beginning
# of the Doubly Linked List
def push(head_ref, new_data):
# Allocate the node
new_node = Node()
# Insert the data
new_node.data = new_data;
# Since we are adding at the beginning,
# prev is always None
new_node.prev = None;
# Link the old list off the new node
new_node.next = (head_ref);
# Change the prev of head node to new node
if ((head_ref) != None):
(head_ref).prev = new_node;
# Move the head to point to the new node
(head_ref) = new_node;
return head_ref
# Function to find the largest
# nodes in the Doubly Linked List
def LargestInDLL(head_ref):
max = None
temp = None
# Initialize two-pointer temp
# and max on the head node
temp = max = head_ref;
# Traverse the whole doubly linked list
while (temp != None):
# If temp's data is greater than
# the max's data, then max = temp
# and return max.data
if (temp.data > max.data):
max = temp;
temp = temp.next;
return max.data;
# Function to create hashset table to
# check Fibonacci numbers
def createHash( hashset, maxElement):
prev = 0
curr = 1;
hashset.add(prev);
hashset.add(curr);
# Inserting the Fibonacci numbers
# until the maximum element in the
# Linked List
while (curr <= maxElement):
temp = curr + prev;
hashset.add(temp);
prev = curr;
curr = temp;
# Function to delete a node
# in a Doubly Linked List.
# head_ref -. pointer to head node pointer.
# delt -. pointer to node to be deleted
def deleteNode(head_ref, delt):
# Base case
if (head_ref == None or delt == None):
return;
# If the node to be deleted is head node
if (head_ref == delt):
head_ref = delt.next;
# Change next only if node to be
# deleted is not the last node
if (delt.next != None):
delt.next.prev = delt.prev;
# Change prev only if node to be
# deleted is not the first node
if (delt.prev != None):
delt.prev.next = delt.next;
# Finally, free the memory
# occupied by delt
del(delt);
return;
# Function to delete all fibonacci nodes
# from the doubly linked list
def deleteFibonacciNodes(head_ref):
# Find the largest node value
# in Doubly Linked List
maxEle = LargestInDLL(head_ref);
# Creating a set containing
# all the fibonacci numbers
# upto the maximum data value
# in the Doubly Linked List
hashset = set()
createHash(hashset, maxEle);
ptr = head_ref;
next=None
# Iterating through the linked list
while (ptr != None):
next = ptr.next;
# If node's data is fibonacci,
# delete node 'ptr'
if (ptr.data in hashset):
deleteNode(head_ref, ptr);
ptr = next;
# Function to print nodes in a
# given doubly linked list
def printList(head):
while (head != None):
print(head.data, end = ' ')
head = head.next;
# Driver program
if __name__=='__main__':
head = None;
# Create the doubly 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);
print("Original List: ", end='')
printList(head);
deleteFibonacciNodes(head);
print("\nModified List: ", end='')
printList(head);
# This code is contributed by rutvik_56
Producción:
Original List: 15 16 8 6 13 Modified List: 15 16 6
Complejidad temporal: O(N) , donde N es el número total de Nodes.
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