CareerCup

1. let pointer p1 and p2 and p3 are pointing to the head of linked list.
2. move p1 by one node and p2 by two node.
3. if loop exists p1 and p2 will meet at some node.
4. now start moving p3 and p1(or p2) by one node. p3 and p1(or p2) will meet at the node from where loop starts.

Proof:
let x=number of nodes from head to the node from where loop starts.
let y=number of nodes from the node from where the loop starts to the node where p1 and p2 meets.
let z=number of nodes from the node on which p1 and p2 meets to the node where loop starts.

Number of node traveled by p1 is x+y.
Number of node traveled by p2 is x+y+z+y.
since p2 is as fast as twice of p1 therefore
2(x+y) = x+y+z+y
=>x=z.
Thus the node from which loop starts is equidistant from the head and the node where p1 and p2 meets.

wiki Cycle_detection would help.

I think either CareerCup 150 or Programming Interviews Exposed has this exact problem and the solution is as described by Tulley.

int validateCircularList(node* head) {
	map<signed int, int> addList;
	map<signed int, int>::iterator it;
	node* tail;

	//add head
	int add = (int) (head);
	cout << endl;
	cout << endl;

	addList.insert(pair<signed int, int> (add, head->val));

	//rest of the nodes
	head = head->next;
	do {
		int tempAdd = (int) (head);
		it = addList.find(tempAdd);

		if (it == addList.end()) {
			addList.insert(pair<signed int, int> (tempAdd, head->val));
			tail = head;
			if (head->next != NULL)
				head = head->next;
			else
				return 0;
		}
		else {
			cout << endl << "LOOP exists:" << endl;
			cout << "loop starts = " << (head->val) << "and Loop ends = "
					<< tail->val << endl;
			return 1;
		}
	} while (1);
	return 0;
}

I won't type the code here but I did the same problem few days back.

Algo----
take two pointers p1 & p2.
begin a loop moving p1 one node at a time and p2 2 nodes at a time while one of them reaches end OR they meet at some node.
If they meet loop is detected.

Now at the point where loop is detected start moving p2 one node at a time and begin a counter(keeping p1 at same position).

When they meet again this counter will give the size of loop.

Now when we have the size of the loop we start from the beginning node again.
Now offset p2 counter no. of nodes from the start.

Now keep moving p1 and p2 one node at a time. The point where they meet will give the starting point of the loop. Try to visualize with any example.

for find out the starting of loop in link list,
first findout the node at which both p1 (incremented by 1)& p2 (incremented by 2) are met.
After that always third node from this meeting node is start node of loop, strongly verified.

Amit Singh