リストのループ検出

リストのループ重複検出をするコードを書いてください，という質問は候補者が勉強をしてきたかどうかを見るのに加減の良い問題だと，昨今のインタビューをしていて思った次第である．

 様々な解の仕方があるが，やはりウサギさんとカメさんを期待するだろう．

#include <iostream>

class Node {
// to make code simpler, members are public
public:
 int _data;
 Node* _next;
 Node(int data) :_data(data) {
  _next = NULL;
 }
 ~Node(){}
 Node(Node& n) {
  _data = n._data;
  _next = n._next;
 }
 Node& operator=(Node& n) {
  _data = n._data;
  _next = n._next;
  return *this;
 }
};

void iterate(Node* root) {
 Node* p = root;
 int cnt = 0;
 while (p) {
  std::cout << p->_data << std::endl;
  p = p->_next;
  if (cnt++ >= 100) {
   std::cerr << "!!!! potential loop found" << std::endl;
   return;
  }
 }
}

void add(Node* root, int val) {
 Node* n = new Node(val);
 Node* p = root;
 while (p->_next) {
  p = p->_next;
 }
 p->_next = n;
}

bool detectLoop(Node* root) {
 Node* slow_ptr = root;
 Node* fast_ptr = root;
 while (slow_ptr && fast_ptr && fast_ptr->_next) {
  slow_ptr = slow_ptr->_next;
  fast_ptr = fast_ptr->_next->_next;
  std::cout << slow_ptr->_data << ":" << fast_ptr->_data << std::endl;
  if (slow_ptr == fast_ptr) {
   return true;
  }
 }
 return false;
}

int main() {
 Node r(10);
 add(&r, 32);
 add(&r, 64);
 add(&r, 128);
 // simulate loop here
 r._next->_next->_next->_next = r._next;
 iterate(&r);
 std::cout << "loop exists?" << (detectLoop(&r) ? "TRUE" : "FALSE") << std::endl;
 return 0;
}