チェーンテーブルにループがあるかどうか,入口ノードおよびループの大きさ(C++)を判断する.

このブログでは、上記の問題について詳しく説明しています.チェーンテーブルにループがあるかどうかを判断する---単一チェーンテーブルのループに関する問題
ここではC++の1つのコード実装のみを行い,主にリングチェーンテーブルの構築を含み,リングがあるかどうかおよびリングの大きさを判断する.

#include
#include

using  namespace std;

struct Node {
	int val;
	Node* next;
	Node(int num):val(num),next(nullptr){}
};

Node* CreatCircularList() {
	Node* head = new Node(0);
	Node* ptr = head, *enterNode = nullptr;
	cout << "Please input a number(0 to entry node, q to quit): ";
	int temp;
	bool sign = false;
	while (cin >> temp) {
		Node* newNode = new Node(temp);
		if (!sign&&temp == 0) {
			enterNode = newNode;
			sign = true;
		}
		newNode->next = ptr->next;
		ptr->next = newNode;
		ptr = newNode;
		cout << "Please input a number(0 to entry node, q to quit): ";
	}
	if(sign) ptr->next = enterNode;
	return head->next;
}

bool IsLoop(Node* head) {
	if (head == nullptr || head->next == nullptr) return false;
	Node* low = head->next;
	Node* fast = head->next->next;
	while (fast != nullptr && fast->next != nullptr && fast != low) {
		fast = fast->next->next;
		low = low->next;
	}
	if (fast == low) return true;
	else return false;
}

Node* findEnterVal(Node* head) {
	if (head == nullptr || head->next == nullptr) return nullptr;
	Node* low = head->next;
	Node* fast = head->next->next;
	while (fast != nullptr && fast->next != nullptr && fast != low) {
		fast = fast->next->next;
		low = low->next;
	}
	if (fast == low) {
		low = head;
		while (low != fast) {
			low = low->next;
			fast = fast->next;
		}
		return low;
	}
	else return nullptr;
}

int LoopLength(Node* head) {
	if (!IsLoop(head)) return 0;
	Node* enterNode = findEnterVal(head);
	Node* ptr = enterNode->next;
	int count = 1;
	while (ptr != enterNode) {
		count++;
		ptr = ptr->next;
	}
	return count;
}

int main() {
	Node* head = CreatCircularList();
	cout << "#1 If there is a cycle in it: " << IsLoop(head) << endl;
	Node* temp = findEnterVal(head);
	if (temp != nullptr)
		cout << "#2 Enter node value: " << findEnterVal(head)->val << endl;
	else
		cout << "#2 List is not a cycle!" << endl;
	cout << "#3 Loop length: " << LoopLength(head) << endl;
	return 0;
}