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 few soIutions prior to this. Lets look into an easy but not so commonly used solution.

Sol 5: Find Cycle through List Reversal

We've looked into some classic approaches of Linked List Cycle Finding Methods (Hare and Tortoise) in the previous posts. Lets see a more easier straightforward approach. I am a bit surprised this is not a usually used method.

The idea is pretty simple. Reverse the list!!. If you meet the head in the process of reversal, you've got a cycle. Below is some sample code for this. The exit condition, when you do not find a cycle is when you reach the tail node. Either ways the list needs to be reveresed again, so that we leave the list in its initial state.

void LinkedList::IsLooped1() {

	LNode* prev=NULL;
	LNode* current=NULL;
	LNode* tmp=head;

	while(tmp) {
		prev=current;
		current=tmp;
		tmp=tmp->next;
		if(tmp==head)
 		  cout < < "Found Loop\n";
		current->next=prev;
	}
	head=current;
	Reverse(); //Leave list in original state
}