Trong bài toán này, chúng ta được cho một danh sách liên kết. Nhiệm vụ của chúng ta là tìm tổng các nút chẵn và lẻ trong danh sách liên kết.
Hãy xem ví dụ sau để hiểu bài toán:
Input : danh sách liên kết : 3 -> 2 -> 5 -> 7 -> 1 -> 9 Output : evenSum = 2 ; oddSum = 25
Giải thích −
evenSum = 2 oddSum = 3 + 5 + 7 + 1 + 9 = 25
Phương pháp giải
Một phương pháp đơn giản để giải bài toán là duyệt qua danh sách liên kết và kiểm tra giá trị chẵn hoặc lẻ, sau đó cộng vào tổng tương ứng.
Thuật toán
Bước 1 − Duyệt danh sách liên kết.
Bước 1.1 − Nếu giá trị nút hiện tại là chẵn, cộng vào evenSum.
Bước 1.2 − Nếu giá trị nút hiện tại là lẻ, cộng vào oddSum.
Bước 2 − Trả về oddSum và evenSum.
Ví dụ
Chương trình minh họa cho giải pháp
#include <iostream> using namespace std; struct Node { int data; Node* next; }; void insertNode(Node** root, int item) { Node *ptr = *root, *temp = new Node; temp->data = item; temp->next = NULL; if (*root == NULL) *root = temp; else { while (ptr->next != NULL) ptr = ptr->next; ptr->next = temp; } } bool isEven(int a){ return (a % 2); } void findEvenAndOddSum(Node* root) { int oddSum = 0, evenSum = 0; Node* node = root; while (node != NULL) { if (isEven(node->data)) evenSum += node->data; else oddSum += node->data; node = node->next; } cout<<"Sum of nodes with even value is "<<evenSum<<endl; cout<<"Sum of nodes with odd value is "<<oddSum; } int main() { Node* root = NULL; insertNode(&root, 3); insertNode(&root, 2); insertNode(&root, 5); insertNode(&root, 7); insertNode(&root, 1); insertNode(&root, 9); insertNode(&root, 6); findEvenAndOddSum(root); return 0; }Kết quả
Sum of nodes with even value is 25 Sum of nodes with odd value is 8