ค้นหาความยาวของลูปในรายการที่เชื่อมโยงใน C++

ในปัญหานี้ เราได้รับรายการเชื่อมโยงที่อาจมีการวนซ้ำ งานของเราคือ ค้นหาความยาวของลูปในรายการที่เชื่อมโยง

คำอธิบายปัญหา: เราจำเป็นต้องนับจำนวนโหนดในลูปหากมีลูปไม่เช่นนั้นให้คืนค่า -1

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: ลิงค์ลิสต์ :

ผลลัพธ์: 8

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

ในการแก้ปัญหา ก่อนอื่นเราต้องตรวจสอบว่ารายการที่เชื่อมโยงมีการวนซ้ำหรือไม่ วิธีการตรวจสอบคือการใช้ Floyd's Cycle Finding Algorithm

ใน อัลกอริธึมการค้นหาวัฏจักรของ Floyd เราจะสำรวจรายการที่เชื่อมโยงโดยใช้ตัวชี้สองตัว หนึ่ง lowPointer ที่เพิ่มขึ้น 1 และอีกอันหนึ่งคือ fastPointer ที่จะเพิ่มขึ้น 2 หากตัวเลขทั้งสองมาบรรจบกัน ณ จุดใดจุดหนึ่ง แสดงว่ามีการวนซ้ำไม่เช่นนั้นจะไม่เกิด

หากมีการวนซ้ำ เราต้องนับจำนวนโหนดที่มีอยู่ในวง สำหรับสิ่งนี้เราจะเริ่มจากจุดที่ slowPointer และ fastPointer พบกันแล้วนับจำนวนโหนดที่ข้ามไปยังตำแหน่งกลับ

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

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

ผลลัพธ์

The number of nodes in the loop are 6>]