Tìm độ dài vòng lặp trong danh sách liên kết trong C++

Cho danh sách liên kết có thể chứa vòng lặp. Nhiệm vụ: tìm độ dài của vòng lặp.

Mô tả: Đếm số nút trong vòng lặp nếu có, ngược lại trả về -1.

Ví dụ:

Đầu vào: linked-list:

Đầu ra: 8

Phương pháp giải

Dùng thuật toán Floyd (tortoise and hare) phát hiện vòng lặp: con trỏ chậm tiến 1, con trỏ nhanh tiến 2. Nếu gặp nhau => có vòng lặp.

Sau khi phát hiện, đếm số nút trong vòng lặp từ điểm gặp nhau.

Chương trình minh họa

Ví dụ

#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;
    cout << "The number of nodes in the loop are " << countLoopNode(head);
    return 0;
}

Kết quả

The number of nodes in the loop are 6