数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中查找链表环的长度
在这个问题中，我们得到一个可能包含环的链表。我们的任务是 *查找链表中环的长度*。
**问题描述：**如果链表包含环，我们需要计算环中节点的数量；否则返回 -1。
让我们来看一个例子来理解这个问题：
**输入：**链表
输出：8
解决方案
为了解决这个问题，我们首先需要检查链表是否包含环。一种检查方法是使用 *弗洛伊德判圈算法*。
在**弗洛伊德判圈算法**中，我们将使用两个指针遍历链表。一个 *慢指针* 以速度1递增，另一个 *快指针* 以速度2递增。如果这两个指针在某个点相遇，则存在环；否则不存在。
如果存在环，我们需要计算环中存在的节点数。为此，我们将从 *慢指针* 和 *快指针* 相遇的点开始，然后计算遍历回该位置的节点数。
程序说明了我们解决方案的工作原理：
示例
#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>]
更新于： 2021年1月25日
418 次浏览
广告