Deleting a loop in singly linked list [duplicate]

Question

A loop may occur in singly linked list (SLL).
To delete the loop in the list, first we need to detect the loop in the SLL and then delete the loop.

Can any one tell how to delete the loop in a SLL with pseudo code?
Can we do it using 3 pointers?
Is there any alternate to accomplish the task?

Answer 1

There are many solutions to what you ask. One of the easiest yet inefficient methods consists of reversing the list, while remembering the head node. If you get back to the head node, then you know that a loop exists.

Another way to check is by creating an array containing an int for each node in the list, each time you visit a node, increment its' corresponding value in the array. Then all you have to do is check to see if a value in the array has more than one, and then compare that to where the extra iterations start. This method detects full loops, and small loops. Hopefully this is helpful.