Sum and Product of all Fibonacci Nodes of a Singly Linked List | Python3 implementation to find the sum and product of all of the Fibonacci nodes in a singly linked list ; Node of the singly linked list ; Function to insert a node at the beginning of the singly Linked List ; Allocate new node ; Link the old list to the new node ; Move the head to point the new node ; Function that returns the largest element from the linked list . ; Declare a max variable and initialize with INT_MIN ; Check loop while head not equal to NULL ; If max is less then head -> data then assign value of head -> data to max otherwise node points to next node . ; Function to create a hash table to check Fibonacci numbers ; Inserting the first two numbers in the hash ; Loop to add Fibonacci numbers upto the maximum element present in the linked list ; Function to find the required sum and product ; Find the largest node value in Singly Linked List ; Creating a set containing all the fibonacci numbers upto the maximum data value in the Singly Linked List ; Traverse the linked list ; If current node is fibonacci ; Find the sum and the product ; Driver code ; Create the linked list 15 -> 16 -> 8 -> 6 -> 13
import sys NEW_LINE class Node ( ) : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def push ( head_ref , new_data ) : NEW_LINE INDENT new_node = Node ( new_data ) NEW_LINE new_node . next = head_ref NEW_LINE head_ref = new_node NEW_LINE return head_ref NEW_LINE DEDENT def largestElement ( head_ref ) : NEW_LINE INDENT max = - sys . maxsize NEW_LINE head = head_ref NEW_LINE while ( head != None ) : NEW_LINE INDENT if ( max < head . data ) : NEW_LINE INDENT max = head . data NEW_LINE DEDENT head = head . next NEW_LINE DEDENT return max NEW_LINE DEDENT def createHash ( hash , maxElement ) : NEW_LINE INDENT prev = 0 NEW_LINE curr = 1 NEW_LINE hash . add ( prev ) NEW_LINE hash . add ( curr ) NEW_LINE while ( curr <= maxElement ) : NEW_LINE INDENT temp = curr + prev NEW_LINE hash . add ( temp ) NEW_LINE prev = curr NEW_LINE curr = temp NEW_LINE DEDENT return hash NEW_LINE DEDENT def sumAndProduct ( head_ref ) : NEW_LINE INDENT maxEle = largestElement ( head_ref ) NEW_LINE hash = set ( ) NEW_LINE hash = createHash ( hash , maxEle ) NEW_LINE prod = 1 NEW_LINE sum = 0 NEW_LINE ptr = head_ref NEW_LINE while ( ptr != None ) : NEW_LINE INDENT if ptr . data in hash : NEW_LINE INDENT prod *= ptr . data NEW_LINE sum += ptr . data NEW_LINE DEDENT ptr = ptr . next NEW_LINE DEDENT print ( " Sum ▁ = " , sum ) NEW_LINE print ( " Product ▁ = " , prod ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT head = None ; NEW_LINE head = push ( head , 13 ) NEW_LINE head = push ( head , 6 ) NEW_LINE head = push ( head , 8 ) NEW_LINE head = push ( head , 16 ) NEW_LINE head = push ( head , 15 ) NEW_LINE sumAndProduct ( head ) NEW_LINE DEDENT