TEKPOOL

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions

Sol 3: Two pointer approach (Slow)

The Trivial solutions either took too long for eat more memory. Here is a classic well known appraoch the does constant space O(1) and 0(n) space. This is based of Floyd's cycle-finding algorithm published in the Journal of ACM is his paper Non-Deterministic Algorithms in 1967. There are many variants and improvements to this original solution. These alogrithms can be used for finding cycles in different Data Strucutres. I will explain how it works when applied to Linked Lists

The idea is to use 2 pointers P1 and P2 intialized to the head. Then traverse the two pointers starting from the head, with P1 moving 1 node at a time and P2 moving 2 nodes at a time. If there is indeed a cycle, the nodes will meet inside the loop, otherwise they will reach the tail.

The code below is a simple straightforward illustration of this. There are ways to make this more efficient. I will discuss this in the next post.

bool LinkedList::IsLoopedTwoPointer1() {

     LNode* first=head;
     LNode* second=head;

     while(first && second &&
               first->next && second->next &&
               second->next->next)
    {
	first=first->next;
	second=second->next->next;
	if(first==second)
	{
		cout < < "Found Loop" << endl;
		return true;
	}
     }
     return false;
}