Given a singly linked list. The task is to find the sum of all of the nodes of the given linked list which are divisible by a given number k.
Examples:
Input : List = 7->60->8->40->1 k = 10 Output : Sum = 100 Sum of nodes: 60 + 40 = 100 Input : List = 15->7->3->9->11->5 k = 5 Output : Sum = 20
Algorithm:
- Initialize a pointer ptr with the head of the linked list and a sum variable with 0.
- Start traversing the linked list using a loop until all the nodes get traversed.
- Add the value of the current node to the sum which is divisible by k.
- Increment the pointer to the next node of the linked list i.e. ptr = ptr ->next.
- Repeat the above two steps until the end of the linked list is reached.
- Finally, return the product.
// C++ implementation to find the sum of // nodes which are divisible by k #include <iostream> using namespace std; // A Linked list node struct Node { int data; struct Node* next; }; // Function to insert a node at the // beginning of the linked list void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = new Node; /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // Function to find the sum of // nodes which are divisible by k of the given linked list int sumOfNodes(struct Node* head , int k) { // Pointer to traverse the list struct Node* ptr = head; int sum = 0; // Variable to store product // Traverse the list and // calculate the product while (ptr != NULL) { if(ptr->data%k==0) sum += ptr->data; ptr = ptr->next; } // Return the product return sum; } // Driver Code int main() { struct Node* head = NULL; // create linked list 7->6->8->4->1 push(&head, 70); push(&head, 6); push(&head, 8); push(&head, 4); push(&head, 10); int k=10; cout << "Sum = " << sumOfNodes(head, k); return 0; }
Time Complexity: O(N), where N is the number of nodes in the linked list.
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.