# Remove all nodes from a Doubly Linked List containing Fibonacci numbers

Given a doubly linked list containing **N** nodes, the task is to remove all the nodes from the list which contains Fibonacci numbers.**Examples:**

Input:DLL = 15 <=> 16 <=> 8 <=> 7 <=> 13Output:15 <=> 16 <=> 7Explanation:

The linked list contains two fibonacci numbers 8 and 13.

Hence, these nodes have been deleted.Input:DLL = 5 <=> 3 <=> 4 <=> 2 <=> 9Output:4 <=> 9Explanation:

The linked list contains three fibonacci numbers 5, 3 and 2.

Hence, these nodes have been deleted.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**Approach:** The idea is to use hashing to store and check the Fibonacci numbers.

- Traverse through the entire doubly linked list and obtain the maximum value in the list.
- Now, in order to check for the Fibonacci numbers, build a hash table containing all the Fibonacci numbers less than or equal to the maximum value in the linked list.
- Finally, traverse the nodes of the doubly linked list one by one and remove the nodes which contain Fibonacci numbers as their data value.

Below is the implementation of the above approach:

## 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);` `}` |

## 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 poto 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` |

**Output:**

Original List: 15 16 8 6 13 Modified List: 15 16 6

* Time Complexity: O(N)*, where N is the total number of nodes.