我建议使用Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm。它具有O（n）复杂度，我认为它符合您的要求。

示例代码：

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;
}

有关Wikipedia的更多信息：Floyd的循环查找算法。