CC150 2.6

2_6.cpp

/* CC150 2.6
 * Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
 * DEFINITION
 * Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node,
 * so as to make a loop in the linked list.
 * EXAMPLE
 * Input:A ->B->C->D->E->C [the same C as earlier] 
 * Output:C
 */

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

struct Node {
	char value;
	Node *next = nullptr;
};

// Floyd's cycle-finding algorithm (tortoise and the hare algorithm)
Node *loopHeadFloyd(Node *head)
{
	if (head == nullptr) {
		cerr << "Empty list!" << endl;
		return nullptr;
	}
	if (head->next == nullptr) {
		cerr << "Single element with no loop!" << endl;
		return nullptr;
	}
	Node *slow = head->next, *fast = head->next->next;
	for (; slow != fast && fast != nullptr && fast->next != nullptr;
		slow = slow->next, fast = fast->next->next); // search for first collision
	if (slow != fast) {
		cerr << "List has no loop!" << endl;
		return nullptr;
	}
	slow = head;
	for (; slow != fast; slow = slow->next, fast = fast->next); // search for begining of loop
	return slow;
}

// Brent's cycle-finding algorithm
// searching for the smallest power of two 2^i that is larger than both λ and μ.
Node *loopHeadBrent(Node *head)
{
	int pow = 1, lam = 1;
	Node *slow = head, *fast = head->next;
	while (slow != fast && fast != nullptr) {
		if (pow == lam) { // start a new power of 2
			slow = fast;
			pow *= 2;
			lam = 0;
		}
		fast = fast->next;
		++lam;
	}
	//int mu = 0;
	slow = head; fast = head;
	for (int i = 0; i < lam; ++i)
		fast = fast->next; // the distrance between the hare and toitoise is now λ
	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;
		//++mu;
	}
	return slow;
}

void initNode(Node *head, char c);
void appendNode(Node *head, char c);

int main()
{
	string cstr;
	cin >> cstr; // input list elements
	int n;
	cin >> n; // input index of element where loop begins
	istringstream din(cstr); // built the list from string stream
	char c;
	Node *head = new Node;
	if (din >> c) {
		initNode(head, c);
		while (din >> c) {
			appendNode(head, c);
		}
	}
	Node *loop = head;
	for (int i = 1; loop != nullptr && i != n; ++i)
		loop = loop->next;
	Node *end = head;
	for (; end->next != nullptr; end = end->next);
	end->next = loop; // generate loop
	Node *loopHead = loopHeadFloyd(head); // detect begining of loop
	if (loopHead)
		cout << loopHead->value << endl;
	return 0;
}

void initNode(Node *head, char c) {
	head->value = c;
	head->next = nullptr;
	return;
}

void appendNode(Node *head, char c) {
	Node *newNode = new Node;
	newNode->value = c;
	Node *curr = head;
	while (curr) {
		if (curr->next == nullptr) {
			curr->next = newNode;
			return;
		}
		else
			curr = curr->next;
	}
	return;
}