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

Trong vấn đề này, chúng tôi được cung cấp một danh sách được liên kết có thể chứa các vòng lặp. Nhiệm vụ của chúng ta là tìm độ dài của vòng lặp trong danh sách liên kết.

Mô tả sự cố: chúng ta cần đếm số nút trong vòng lặp nếu nó chứa một vòng lặp, nếu không thì trả về -1.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: danh sách liên kết:

Đầu ra: 8

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

Để giải quyết vấn đề, trước tiên chúng ta cần kiểm tra xem danh sách liên kết có chứa vòng lặp hay không. Một cách tiếp cận để kiểm tra điều này là sử dụng Floyd’s Cycle Finding Algorithm.

Trong Thuật toán tìm kiếm chu kỳ của Floyd, chúng tôi sẽ duyệt qua danh sách được liên kết bằng cách sử dụng hai con trỏ. Một slowPointer tăng 1 và một cái khác là fastPointer điều đó tăng lên 2. Nếu cả hai số gặp nhau tại một thời điểm nào đó thì tồn tại một vòng lặp, ngược lại thì không.

Nếu tồn tại một vòng lặp, chúng ta cần đếm số nút có trong vòng lặp. Đối với điều này, chúng tôi sẽ bắt đầu từ điểm mà slowPointer và fastPointer đáp ứng và sau đó đếm số lượng nút đã đi qua để trở lại vị trí.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

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;
}

Đầu ra

The number of nodes in the loop are 6>]