How can you find if a given linked list has a cycle in it?
Note: Linked list is singly linked list (there is only next pointer no previous pointer).
See Solution: Detect if there is a cycle in the linked list
This can also be solved by using two pointers as we saw in Find nth element from end of linked list and Find middle element of linked list. Take two pointers pointer1 and pointer2, both pointing to head of the linked list initially, now increment pointer1 by one node and pointer2 by two nodes, If at any point of time pointer1 and pointer2 becomes equal then there is a cycle in the linked list, else pointer2 will reach end of the list and will become null eventually.
Code in C
bool isCyclePresent(Node* node){ Node* pointer1 = node; Node* pointer2 = node; while(pointer2 != null && pointer2->next!=null){ pointer1 = pointer1->next; pointer2 = pointer2->next->next; if(pointer1 == pointer2) return true; } return false; }
Facebook Comments
sonu sehrawat says
In while loop,instead of “&&” ,we should hv used ” || “.