How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using a constant amount of memory.

There are quite a few ways to solving this problem. Here are a couple of them:
If you have access to the code, add a new field "visited" to the node structure and initialize it with 0.
typedef struct {
int visited;
...Other fields..
}
Now, start traversing through the linked-list checking for the value of this visited field. If the value
is set to 0, set it to 1 and go to the next node in the list. If you find a node with its visited value set
to 1 before you reach the end of the list, there is a cycle in the linked-list. If not, there is no cycle
present in the list. As you can see this takes O (n) time but requires variable amount of memory.
To accomplish this task using constant memory is much more challenging at first. If you like simple
yet challenging problems, try it yourself before looking at the answer below.
bool cycle_finder(Node *head)
{
Node *p1, *p2;
bool hasCycle = false;
p1 = p2 = head;
while (p2 && p2->next) {
p1 = p1->next;
p2 = p2->next->next;
if (p1 == p2) {
hasCycle = true;
break;
}
}
return hasCycle;
}
Note that p2 is moving through the list twice as fast as p1. If the cycle exists in the list, p1 and p2
will eventually be equal. Otherwise, the loop will terminate as soon as p2 reaches the end of the list.