C program to check loop in linked list

If linked list contains a loop, "slow" and "fast" pointers will eventually meet at the same node, thus indicating that the linked list contains a loop. Algorithm to detect cycle in a linked list Traverse the given linked list and put the address of each node in a Hash table. If you reach a node whose next pointer is NULL, then given linked list doesn't contain s cycle.

A linked list is basically a list that stores its elements in non-contiguous locations. The data part holds whatever data we store in it.

This helps the computer to understand the location of the next data item. The pointer part of the last node is NULL which indicates the end of the list. In the above algorithm, slow and fast pointers meet somewhere in the loop which might not be the start or end node of the loop. Note: To place the far pointer as far as the size of the loop, we can first point the far pointer to the first node. Point another pointer, say ptr , to next of any loop node say where slow and fast met.

Keep moving far and ptr until ptr comes back to the loop node. From this output, we can see that after removing the loop, we got the original list that ends with 18 node. So the last node again points to NULL. We can have a simpler solution but with higher memory requirement and time complexity O N 2.

Here the value part is also a pointer instead of node. I write here to help the readers learn and understand computer programing, algorithms, networking, OS concepts etc. I have 20 years of working experience in computer networking and industrial automation.

View all posts by Srikanta. Sign up using Facebook. Sign up using Email and Password. Post as a guest Name. Email Required, but never shown. The Overflow Blog. Podcast Making Agile work for data science. Stack Gives Back Featured on Meta.

New post summary designs on greatest hits now, everywhere else eventually.