ตรวจสอบ Linked List ว่าเป็น Circular Linked List ใน C++

Circular Linked List คืออะไร?

Linked List ที่โหนดสุดท้ายชี้กลับไปที่ head (หรือโหนดแรก) ทำให้เป็นวงกลม ไม่มี NULL ที่ปลาย

วิธีตรวจสอบ

1. เก็บ pointer head ไว้
2. เริ่มจาก head->next ท่องต่อไป
3. ถ้าเจอ NULL → ไม่ใช่ Circular
4. ถ้าเจอ head อีกครั้ง → เป็น Circular

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

#include <iostream>
using namespace std;

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

Node* getNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->next = nullptr;
    return node;
}

bool isCircularList(Node* head) {
    if (head == nullptr) return true; // Empty list ถือว่า circular
    
    Node* curr = head->next;
    while (curr != nullptr && curr != head) {
        curr = curr->next;
    }
    return curr == head;
}

int main() {
    // สร้าง Circular Linked List: 10 → 20 → 30 → 40 → 50 → (กลับไป 10)
    Node* head = getNode(10);
    head->next = getNode(20);
    head->next->next = getNode(30);
    head->next->next->next = getNode(40);
    head->next->next->next->next = getNode(50);
    head->next->next->next->next->next = head; // ทำให้เป็น circular
    
    if (isCircularList(head))
        cout << "The list is circular" << endl;
    else
        cout << "The list is NOT circular" << endl;
    
    // ทดสอบ Normal List
    Node* normal = getNode(1);
    normal->next = getNode(2);
    normal->next->next = getNode(3);
    
    if (isCircularList(normal))
        cout << "Normal list is circular" << endl;
    else
        cout << "Normal list is NOT circular" << endl;
    
    return 0;
}

ผลลัพธ์

The list is circular
Normal list is NOT circular

วิธีอื่น: Floyd's Cycle Detection (Tortoise & Hare)

ใช้ 2 pointers: slow (ก้าว 1) และ fast (ก้าว 2) ถ้าพบกัน → มี cycle

bool hasCycle(Node* head) {
    if (!head) return false;
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

วิธีนี้ดีกว่าเพราะตรวจจับ cycle ได้ทุกแบบ (ไม่จำเป็นต้องกลับไป head พอดี)

ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(1)