在 C++ 中查找链表中循环的长度
c++server side programmingprogramming
在此问题中，我们给出了一个可能包含循环的链表。我们的任务是找出链表中循环的长度。
问题描述：如果循环包含循环，我们需要计算循环中的节点数，否则返回 -1。
让我们举一个例子来理解这个问题，
输入：linked-list :
输出：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<<"循环中的节点数为"<<countLoopNode(head);
return 0;
}
输出
循环中的节点数为 6>]
