หาความยาวของลูปใน Linked List ใน C++

โจทย์

ได้รับ Linked List ที่อาจมีลูป (Loop) ทางเราต้อง หาความยาวของลูปใน Linked List

ตัวอย่าง

Input: Linked List ที่มีลูป (ภาพ)

Output: 8 (ตัวอย่างในโจทย์) / 6 (ตัวอย่างในโค้ด)

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

ใช้ Floyd's Cycle Finding Algorithm (Tortoise and Hare):

1. ใช้ Pointer สองตัว: Slow (ก้าวละ 1) และ Fast (ก้าวละ 2)
2. ถ้าพบกัน แสดงว่ามีลูป
3. จากจุดที่พบกัน นับจำนวนโหนดจนกลับมาที่จุดเดิม = ความยาวลูป

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

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

int countLoopNodespoint(struct Node* n) {
    int res = 1;
    struct Node* temp = n;
    while (temp->next != n) { res++; temp = temp->next; }
    return res;
}

int countLoopNode(struct Node* list) {
    struct Node *slowPtr = list, *fastPtr = list;
    while (slowPtr && fastPtr && fastPtr->next) {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;
        if (slowPtr == fastPtr) return countLoopNodespoint(slowPtr);
    }
    return 0;
}

struct Node* newNode(int key) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = key; temp->next = NULL; return temp;
}

int main() {
    struct Node* head = newNode(1);
    head->next = newNode(2); head->next->next = newNode(3);
    head->next->next->next = newNode(4); head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next->next = newNode(7);
    head->next->next->next->next->next->next->next = head->next; // loop at node 2
    cout << "The number of nodes in the loop are " << countLoopNode(head);
    return 0;
}

ผลลัพธ์

The number of nodes in the loop are 6