The project is to test the existence of a loop in a linked
list. A loop in a linked list happens when the pointer of one element in the
list points to a different element in the same list. In this case, the list is
endless when you walk through the list by the pointers. Now you need to find an
algorithm that can find out whether any linked list contains a loop, providing
that:
- The length of the linked list is unknown,
- Only limited memory resource is available, i.e.
you only have a constant number of bytes of memory that is large enough
to find the result, but the number is independent of the length of the
linked list,
- The time required to find the result is at most
linear to the length of the linked list, and
- You
can change the content of the elements in the list, only if you can
restore them at the end of the program.
|