Trong bài toán này, chúng tôi đưa ra một danh sách liên kết. Nhiệm vụ của chúng tôi là in tổng các nút thay thế của danh sách được liên kết.
Danh sách được liên kết là một chuỗi cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết.
Bây giờ, hãy quay lại vấn đề. Ở đây, chúng tôi sẽ thêm các nút thay thế của danh sách liên kết. Điều này có nghĩa là chúng ta sẽ thêm các nút là các vị trí 0, 2, 4, 6,…
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
4 → 12 → 10 → 76 → 9 → 26 → 1
Đầu ra
24
Giải thích
considering alternate strings − 4 + 10 + 9 + 1 = 24
Để giải quyết vấn đề này, chúng tôi sẽ truy cập từng nút một và cho mọi nút tổ. Chúng tôi sẽ thêm giá trị vào tổng. Để kiểm tra các nút, chúng tôi sẽ sử dụng một cờ.
Điều này có thể được thực hiện bằng cách sử dụng lặp lại hoặc đệ quy. Chúng ta sẽ thảo luận cả hai ở đây,
Ví dụ
Phương pháp lặp lại
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = (*head_ref);
(*head_ref) = newNode;
}
int sumAlternateNodeIt(struct Node* head) {
bool flag = true;
int sum = 0;
while (head != NULL){
if (flag)
sum += head->data;
flag = !flag;
head = head->next;
}
return sum;
}
int main(){
struct Node* head = NULL;
pushNode(&head, 54);
pushNode(&head, 12);
pushNode(&head, 87);
pushNode(&head, 1);
pushNode(&head, 99);
pushNode(&head, 11);
cout<<"The sum of alternate nodes is "<<sumAlternateNodeIt(head);
return 0;
} Đầu ra
The sum of alternate nodes is 24
Ví dụ
Phương pháp tiếp cận đệ quy
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void sumAlternateNodeRec(struct Node* node, int& sum, bool flag = true){
if (node == NULL)
return;
if (flag == true)
sum += (node->data);
sumAlternateNodeRec(node->next, sum, !flag);
}
int main(){
struct Node* head = NULL;
pushNode(&head, 54);
pushNode(&head, 12);
pushNode(&head, 87);
pushNode(&head, 1);
pushNode(&head, 99);
pushNode(&head, 11);
int sum = 0;
sumAlternateNodeRec(head, sum, true);
cout<<"The sum of alternate nodes is "<<sum;
return 0;
} Đầu ra
The sum of alternate nodes is 24