Mean of distinct odd fibonacci nodes in a Linked List | C ++ program to implement the above approach ; Structure of a singly Linked List ; Stores data value of a Node ; Stores pointer to next Node ; Function to insert a node at the beginning of the singly Linked List ; Create a new Node ; Insert the data into the Node ; Insert pointer to the next Node ; Update head_ref ; Function to find the largest element from the linked list ; Stores the largest element in the linked list ; Iterate over the linked list ; If max is less than head -> data ; Update max ; Update head ; Function to store all Fibonacci numbers up to the largest element of the list ; Store all Fibonacci numbers up to Max ; Stores first element of Fibonacci number ; Stores second element of Fibonacci number ; Insert prev into hashmap ; Insert curr into hashmap ; Insert all elements of Fibonacci numbers up to Max ; Stores current fibonacci number ; Insert temp into hashmap ; Update prev ; Update curr ; Function to find the mean of odd Fibonacci nodes ; Stores the largest element in the linked list ; Stores all fibonacci numbers up to Max ; Stores current node of linked list ; Stores count of odd Fibonacci nodes ; Stores sum of all odd fibonacci nodes ; Traverse the linked list ; if the data value of current node is an odd number ; if data value of the node is present in hashmap ; Update cnt ; Update sum ; Remove current fibonacci number from hashmap so that duplicate elements can 't be counted ; Update curr ; Return the required mean ; Driver Code ; Stores head node of the linked list ; Insert all data values in the linked list
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * next ; } ; void push ( Node * * head_ref , int new_data ) { Node * new_node = new Node ; new_node -> data = new_data ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } int largestElement ( struct Node * head_ref ) { int Max = INT_MIN ; Node * head = head_ref ; while ( head != NULL ) { if ( Max < head -> data ) { Max = head -> data ; } head = head -> next ; } return Max ; } set < int > createHashMap ( int Max ) { set < int > hashmap ; int prev = 0 ; int curr = 1 ; hashmap . insert ( prev ) ; hashmap . insert ( curr ) ; while ( curr <= Max ) { int temp = curr + prev ; hashmap . insert ( temp ) ; prev = curr ; curr = temp ; } return hashmap ; } double meanofnodes ( struct Node * head ) { int Max = largestElement ( head ) ; set < int > hashmap = createHashMap ( Max ) ; Node * curr = head ; int cnt = 0 ; double sum = 0.0 ; while ( curr != NULL ) { if ( ( curr -> data ) & 1 ) { if ( hashmap . count ( curr -> data ) ) { cnt ++ ; sum += curr -> data ; hashmap . erase ( curr -> data ) ; } } curr = curr -> next ; } return ( sum / cnt ) ; } int main ( ) { Node * head = NULL ; push ( & head , 5 ) ; push ( & head , 21 ) ; push ( & head , 8 ) ; push ( & head , 12 ) ; push ( & head , 3 ) ; push ( & head , 13 ) ; push ( & head , 144 ) ; push ( & head , 6 ) ; cout << meanofnodes ( head ) ; return 0 ; }