C++의 연결 목록에서 루프 길이 찾기

이 문제에서는 루프를 포함할 수 있는 연결 목록이 제공됩니다. 우리의 임무는 연결된 목록에서 루프의 길이를 찾는 것입니다.

문제 설명: 루프가 포함되어 있으면 루프의 노드 수를 계산해야 합니다. 그렇지 않으면 -1을 반환합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: 연결 목록 :

출력: 8

솔루션 접근 방식

문제를 해결하려면 먼저 연결 목록에 루프가 포함되어 있는지 확인해야 합니다. 이를 확인하기 위한 접근 방식은 Floyd의 주기 찾기 알고리즘을 사용하는 것입니다.

Floyd의 주기 찾기 알고리즘 에서 두 개의 포인터를 사용하여 연결 목록을 탐색합니다. 하나의 slowPointer 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>]