C++のリンクリストでループの長さを見つける

この問題では、ループを含む可能性のあるリンクリストが表示されます。私たちのタスクは、リンクリストでループの長さを見つけることです。

問題の説明： ループが含まれている場合はループ内のノード数をカウントする必要があります。それ以外の場合は-1を返します。

問題を理解するために例を見てみましょう。

入力： リンクリスト：

出力： 8

ソリューションアプローチ

この問題を解決するには、まずリンクリストにループが含まれているかどうかを確認する必要があります。これを確認するためのアプローチは、フロイドの循環検出アルゴリズムを使用することです。

フロイドの循環検出アルゴリズムでは、 2つのポインタを使用してリンクリストをトラバースします。 1つのslowPointer これは1つ増え、もう1つは fastPointer ある時点で両方の数値が一致する場合はループが存在し、そうでない場合はループが存在しません。

ループが存在する場合は、ループ内に存在するノードの数を数える必要があります。このために、 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>]