// Given a circular linked list, implement an algorithm which returns node at
// the beginning of the loop.
// DEFINITION
// Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an
// earlier node, so as to make a loop in the linked list.
// EXAMPLE
// input: A -> B -> C -> D -> E -> C [the same C as earlier]
// output: C

#include <list>
#include <cassert>
#include <set>

int FirstNodeInCycle(std::list<int> list) {
  std::set<int> visited;
  for (auto it = list.begin(); it != list.end(); ++it) {
    if (visited.find(*it) != visited.end()) {
      return *it;
    }
    visited.insert(*it);
  }
  return -1;
}

int main(int argc, char* argv[]) {
  assert(FirstNodeInCycle(std::list<int>({1,2,3,4,5,6,3,7})) == 3);
  assert(FirstNodeInCycle(std::list<int>({})) == -1);
  assert(FirstNodeInCycle(std::list<int>({1, 2, 3})) == -1);
  return 0;
}