Linked List: Detect a Cycle in a linked list – List Reversal

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 Loopn";
    current->next=prev;
}
head=current;
Reverse(); //Leave list in original state

}