นับจำนวนโหนดในรายการเชื่อมโยงแบบวงกลมใน C++

เราได้รับรายการเชื่อมโยงแบบวงกลม (Circular Linked List) งานคือการนับจำนวนโหนดทั้งหมดในรายการ

รายการเชื่อมโยงแบบวงกลม

โหนดสุดท้ายชี้กลับไปที่โหนดแรก สามารถเป็น Singly หรือ Doubly Linked List ได้ ในตัวอย่างนี้ใช้ Singly Linked List

ตัวอย่าง

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

แนวทางการแก้ปัญหา

• สร้างโครงสร้างโหนด (data, next)
• ฟังก์ชัน push() เพิ่มโหนดและเชื่อมโหนดสุดท้ายกับโหนดแรก
• ฟังก์ชันนับ: ใช้ do-while วนจาก head จนกลับมาที่ head อีกครั้ง

ตัวอย่างโค้ด C++

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

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

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

int countNodes(Node* head) {
    if (head == nullptr) return 0;
    Node* temp = head;
    int count = 0;
    do {
        temp = temp->next;
        count++;
    } while (temp != head);
    return count;
}

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

ผลลัพธ์

count of nodes are: 4