Đếm nút trong danh sách liên kết vòng C++

Cho một danh sách liên kết vòng (circular linked list), nhiệm vụ là đếm số nút (nodes) có trong danh sách.

Danh sách liên kết vòng là gì?

Là biến thể của linked list nơi nút cuối trỏ về nút đầu, tạo thành một vòng tròn. Có thể là singly hoặc doubly linked list.

Ví dụ

Input - nodes: 20, 1, 2, 3, 4, 5 Output - count of nodes: 6

Input - nodes: 20, 1, 2, 3, 4, 5, 7, 8, 9, 12 Output - count of nodes: 10

Phương pháp tiếp cận

• Định nghĩa struct node: data, next
• Hàm push() thêm nút mới và duy trì tính vòng tròn
• Hàm count_fun(): duyệt qua vòng lặp do-while cho đến khi quay về head

Ví dụ code C++

#include <stdio.h>
#include <stdlib.h>

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

void push(struct node** head_ref, int data) {
    struct node* ptr1 = (struct node*)malloc(sizeof(struct node));
    struct 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; // nút đầu tiên trỏ về chính nó
    }
    *head_ref = ptr1;
}

int count_fun(struct node* head) {
    struct node* temp = head;
    int result = 0;
    if (head != NULL) {
        do {
            temp = temp->next;
            result++;
        } while (temp != head);
    }
    return result;
}

int main() {
    struct node* head = NULL;
    push(&head, 10);
    push(&head, 20);
    push(&head, 30);
    push(&head, 40);
    printf("count of nodes are: %d", count_fun(head));
    return 0;
}

Kết quả

count of nodes are: 4