Check linkedlist circularity

Question

I need a method that takes a linkedlist as a parameter and return true or false if it is circular or not.

ex:circular linkedlist means there is node pointes to any previous node. I forgot to tell some constraints, I can not use any datastructure or dynmaic memory allocations. I can use local variables only and the alogrithm can be done in n steps as someone said to me (I am thinking now to use two pointers?)

Answer 1

Standard hash count applies:

function has_loop(list):
    foreach node in list:
        address = address_of(node.next);
        element = hashtable.get(address);
        if (element == NULL):
            hashtable.put(address)
        else:
            return true
    return false

EDIT: As per the accepted answer's second link, this works but is inefficient, meaning there are lots of more efficient solutions.

Answer 2

This is trivial.

previousnodes ← set()
previousnodes.add(firstnode)
currentnode ← firstnode.next
while (currentnode in previousnodes) || (currentnode != null):
  previousnodes.add(currentnode)
  currentnode ← currentnode.next
when (currentnode = 0) return false
return true

Answer 3

I believe you're looking for Floyd's Cycle-Finding Algorithm. There's a better explanation than I could give of it over here.

There are also a couple of implementations in C and Scheme with documentation over here.