資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告