Given a circular singly linked list containing N nodes, the task is to remove all the nodes from the list which contains Fibonacci data values.
Examples:
Input: CLL = 9 -> 11 -> 34 -> 6 -> 13 -> 20
Output: 9 -> 11 -> 6 -> 20
Explanation:
The list contains 2 fibonacci data values 32 and 13.
Therefore, the nodes containing this data has been deleted
Input: 5 -> 11 -> 16 -> 21 -> 17 -> 10
Output: 11 -> 16 -> 17 -> 10
Explanation:
The list contains 2 fibonacci data values 5 and 21.
Therefore, the nodes containing this data has been deleted
Approach: The idea is to use hashing to precompute and store the Fibonacci numbers, and then check if a node contains a Fibonacci value in O(1) time.
- Traverse through the entire circular singly 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 circular singly linked list.
- Finally, traverse the nodes of the circular singly linked list one by one and check if the node contains Fibonacci numbers as their data value. Remove the nodes which have Fibonacci value.
Below is the implementation of the above idea:
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 nodestruct Node { int data; struct Node* next;};// Function to insert a node at the beginning// of a Circular linked listvoid 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 listvoid 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 listint 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 numbersvoid 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 listvoid 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 listvoid printList(struct Node* head){ struct Node* temp = head; if (head != NULL) { do { printf("%d ", temp->data); temp = temp->next; } while (temp != head); }}// Driver codeint 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 listimport java.util.*;class GFG{ // Structure for a nodestatic class Node { int data; Node next;}; // Function to insert a node at the beginning// of a Circular linked liststatic 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 liststatic 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 liststatic 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 numbersstatic 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 liststatic 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 liststatic void printList(Node head){ Node temp = head; if (head != null) { do { System.out.printf("%d ", temp.data); temp = temp.next; } while (temp != head); }} // Driver codepublic 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 listusing System;using System.Collections.Generic;class GFG{ // Structure for a nodeclass Node { public int data; public Node next;}; // Function to insert a node at the beginning// of a Circular linked liststatic 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 liststatic 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 liststatic 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 numbersstatic 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 liststatic 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 liststatic void printList(Node head){ Node temp = head; if (head != null) { do { Console.Write("{0} ", temp.data); temp = temp.next; } while (temp != head); }} // Driver codepublic 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 nodeclass 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 traversingvar 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 emptyvar 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> |
Output:
9 11 6 20
Time Complexity: O(n + log(maxElement)) (actual generation hash table of fibonacci no. till maxElement required O(log(maxElement)) time + O(n) for traversing LinkList containing node n)
Auxiliary Space: O(log(maxElement)) (storing fibonacci number’s in hash)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
