Floyd's Cycle Finding Algorithm

...

Floyd's Cycle Finding Algorithm, also known as the tortoise and hare algorithm, is used to detect cycles in a linked list or any sequence of elements. It works by using two pointers, one moving at a slower pace (tortoise) and the other at a faster pace (hare), to traverse the sequence. If there is a cycle present, the two pointers will eventually meet at the same node.

The algorithm consists of the following steps:

1. Initialize two pointers, the tortoise and the hare, to the starting node of the sequence.
2. Move the tortoise one step at a time and the hare two steps at a time.
3. Continue moving the pointers until they either meet at the same node or reach the end of the sequence. If they reach the end without meeting, there is no cycle present.
4. If the pointers meet at the same node, it indicates the presence of a cycle in the sequence.

The algorithm can be summarized using the following pseudocode:

class Node {
public:
	int data;
	Node* next;

	Node(int data)
	{
		this->data = data;
		next = NULL;
	}
};

Node* head = NULL;

class Linkedlist {
public:
	void insert(int value){
		Node* newNode = new Node(value);
		if (head == NULL)
			head = newNode;
		else {
			newNode->next = head;
			head = newNode;
		}
	}
	bool detectLoop(){
		Node *slowPointer = head,
			*fastPointer = head;

		while (slowPointer != NULL
			&& fastPointer != NULL
			&& fastPointer->next != NULL) {
			slowPointer = slowPointer->next;
			fastPointer = fastPointer->next->next;
			if (slowPointer == fastPointer)
				return 1;
		}
		return 0;
	}
};

int main(){
	Linkedlist l1;
	l1.insert(10);
	l1.insert(20);
	l1.insert(30);
	l1.insert(40);
	l1.insert(50);

	Node* temp = head;
	while (temp->next != NULL)
		temp = temp->next;

	temp->next = head;

	if (l1.detectLoop())
		cout << "Loop exists in the"
			<< " Linked List" << endl;
	else
		cout << "Loop does not exists "
			<< "in the Linked List" << endl;
	return 0;
}
Copy