Tổng các nút cách nhau (alternate nodes) trong danh sách liên kết trong C++

Cho danh sách liên kết, tính tổng các nút cách nhau (vị trí 0, 2, 4, 6...).

Ví dụ

Đầu vào: 4 → 12 → 10 → 76 → 9 → 26 → 1

Đầu ra: 24

Giải thích: 4 + 10 + 9 + 1 = 24

Phương pháp 1: Lặp (Iterative)

Dùng flag true/false luân phiên.

int tongCanhLeLap(Node* head) {
    bool flag = true;
    int tong = 0;
    while (head) {
        if (flag) tong += head->data;
        flag = !flag;
        head = head->next;
    }
    return tong;
}

Phương pháp 2: Đệ quy (Recursive)

void tongCanhLeDeQuy(Node* node, int &tong, bool flag = true) {
    if (!node) return;
    if (flag) tong += node->data;
    tongCanhLeDeQuy(node->next, tong, !flag);
}

Ví dụ mã nguồn hoàn chỉnh

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void themDau(Node** head, int data) {
    Node* n = new Node();
    n->data = data; n->next = *head; *head = n;
}

// Lặp
int tongCanhLeLap(Node* head) {
    bool flag = true; int tong = 0;
    while (head) { if (flag) tong += head->data; flag = !flag; head = head->next; }
    return tong;
}

// Đệ quy
void tongCanhLeDeQuy(Node* node, int &tong, bool flag = true) {
    if (!node) return;
    if (flag) tong += node->data;
    tongCanhLeDeQuy(node->next, tong, !flag);
}

int main() {
    Node* head = NULL;
    themDau(&head, 54); themDau(&head, 12); themDau(&head, 87);
    themDau(&head, 1); themDau(&head, 99); themDau(&head, 11);
    
    cout << "Lặp: " << tongCanhLeLap(head) << endl;
    
    int tong = 0;
    tongCanhLeDeQuy(head, tong);
    cout << "Đệ quy: " << tong << endl;
    return 0;
}

Kết quả

Lặp: 24
Đệ quy: 24