Career 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

career2.6.cpp

#include "stdafx.h"
#include <iostream>
#include <map>
using namespace std;

template <class T>
struct node{
  T data;
	node *next;
};


template <class T>
class linkedList{
private:
	node<T> *head;
public:
	linkedList(){
		head = NULL;
	};

	node<T> *newNode(T val){
		node<T> *n = new node<T>;
		n->data = val;
		n->next = NULL;
		return n;
	};

	void createList(T a[], int length){
		if(head==NULL)
			head = newNode(a[0]);
		node<T> *curr = head;
		for(int i=1;i<length;i++){
			node<T> *n = newNode(a[i]);
			curr->next = n;
			curr = n;
		}
	};

	void printAll(){
		node<T> *curr = head;
		while(curr!=NULL){
			cout << curr->data << " ";
			curr = curr->next;
		}
	};

	int length(){
		node<T> *curr=head;
		int count = 0;
		while(curr!=NULL){
			++count;
			curr=curr->next;
		}
		return  count;
	};

	void addFront(T val){
		node<T> *n = newNode(val);
		n->next = head;
		head = n;
	}

	void addTail(T val){
		node<T> *curr = head;
		if(head==NULL)
			head = newNode(val);
		else{
			while(curr->next!=NULL)
				curr=curr->next;
			node<T> *n = newNode(val);
			curr->next = n;
		}

	};

	node<T> *headNode(){
		return head;
	};

};

template <class T>
node<T> *nodeInLoop(node<T> *head){
	if(head==NULL) return NULL;
	map<T,bool> table;
	node<T> *curr=head;
	while(true)
	{
		if(table[curr->data]){
			return curr;
		}		
		else{
			table[curr->data] = true;
			curr=curr->next;
		}
	}
}






int _tmain(int argc, _TCHAR* argv[])
{
	linkedList<int> ll;
	int a[] = {1,2,3,4,90,7,8,4};
	ll.createList(a,8);
	cout << nodeInLoop<int>(ll.headNode())->data << endl;
	

	char letter;
	cin >> letter;

	return 0;
}