Tổng các nút trong danh sách liên kết vòng (Circular Linked List) trong C++

Cho danh sách liên kết vòng, tính tổng giá trị tất cả các nút.

Định nghĩa: Danh sách liên kết vòng: nút cuối trỏ về nút đầu, nút đầu trỏ về nút cuối (có thể đơn hoặc đôi).

Ví dụ

Đầu vào: 14 → 1 → 7 → 9 → 2 → 6 (vòng)

Đầu ra: 39

Giải thích: 14+1+7+9+2+6 = 39

Thuật toán

int tinhTong(Node* head) {
    if (!head) return 0;
    Node* ptr = head;
    int tong = 0;
    do {
        tong += ptr->data;
        ptr = ptr->next;
    } while (ptr != head);
    return tong;
}

Ví dụ mã nguồn

#include <iostream>
using namespace std;

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

void themDau(Node** head_ref, int data) {
    Node* ptr1 = new Node();
    Node* temp = *head_ref;
    ptr1->data = data;
    ptr1->next = *head_ref;
    if (*head_ref != NULL) {
        while (temp->next != *head_ref) temp = temp->next;
        temp->next = ptr1;
    } else ptr1->next = ptr1;
    *head_ref = ptr1;
}

int tinhTong(Node* head) {
    if (!head) return 0;
    Node* ptr = head;
    int tong = 0;
    do {
        tong += ptr->data;
        ptr = ptr->next;
    } while (ptr != head);
    return tong;
}

int main() {
    Node* head = NULL;
    themDau(&head, 4); themDau(&head, 7); themDau(&head, 12);
    themDau(&head, 1); themDau(&head, 9); themDau(&head, 6);
    cout << "Tổng danh sách vòng: " << tinhTong(head);
    return 0;
}

Kết quả

Tổng danh sách vòng: 39