How to find a node inside a linked list referring another node

Question

If we have a linked list with 10 nodes and 6th node is referring to the 2nd node. How can we able to determine that a loop exists inside

Answer 1

This situation can't happen because if you have 10 nodes then the last node should be null in the linked list. As you're saying above then your 5th node should be null in this situation and you will only have 5 elements. If you are using circular linked list then you can check

 '(last->data== (first++)->data)'

Answer 2

There are some interesting cycle detection algorithms, the most famous is the "the tortoise and the hare" algorithm (aka Floyd's cycle detection). It's based on the idea that if the hare walks twice as fast a the tortoise, iff there is a cycle, they will meet each other again.

Brent's algorithm is a bit more complicated, but tends to do fewer evaluation of the "next" function (here: follows fewer pointers).

There are ways to use even fewer evaluations. As far as I know all of them are based on using some more storage. The most obvious way is to just keep a hash table of "nodes seen so far", and detect a cycle when you're about to add a node to it that's already in there, immediately detecting a node that you see for the second time but taking O(n) space. Gosper's loop detection algorithm takes only O(log n) space, and is far more interesting (a bit tricky to understand perhaps). There's also a tunable (space vs evaluations) algorithm based on using multiple stacks (article contains links to even more algorithms).