How to determine if a linked list has a cycle using only two memory locations

I would suggest using Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm. It has O(n) complexity and I think it fits your requirements.

Example code:

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

More info on Wikipedia: Floyd's cycle-finding algorithm.

Absolutely. One solution indeed can be traversing the list with both pointers, one travelling at twice the rate of the other.

Start with the 'slow' and the 'fast' pointer pointing to any location in the list. Run the traversal loop. If the 'fast' pointer at any time comes to coincide with the slow pointer, you have a circular linked list.

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}

You can use the Turtle and Rabbit algorithm.

Wikipedia has an explanation too, and they call it "Floyd's cycle-finding algorithm" or "Tortoise and hare"