Finding a circle in a linked list with lookup table

Question

I'm trying to find a circle in a linked list, and return the node at the beginning of the circle. For example, if the list was A -> B -> C -> D -> C -- we would return C

Here is my code:

ListNode<T> * findCircle()
{
  map<ListNode<T>*, bool> addresses;

  ListNode<T>* node = head;

  if(addresses.find(node)->second)
    cout << " wtf " << endl;

  while(node)
  { 
    if((addresses.find(node))->second)
    {
      return node;
    } 
    else
      addresses.insert(pair<ListNode<T>*,bool>(node, 1));

    node = node->next;
  }

  return NULL;

}

I have a few questions:

1) is this the right way to approach the problem

2) am I using the most efficient ways to lookup/insert the keys and values into the table

3) why is it not working? When I check in the map for head, before I've inserted head, it still executes that if statement and prints "wtf". My algorithm is to insert the node as a key with a true value if it is not found in the map, otherwise return the node if the key is already in the map.

I tried doing this with std::set but it gave me trouble, so I switched to map. What baffles me is that the following code works (Code to remove duplicates in a linked list, using a lookup table) using exactly the same methodology.

  void removeDuplicates()
    {
      map<T, bool> listData;

      ListNode<T> *node;
      ListNode<T> *prev = node;
      for(node = head; node; node = node->next)
      {
        if(listData.find(node->data)->second)
        {
          prev->next = node->next;
          delete node;
        }
        else
        {
          listData.insert( pair<T, bool>(node->data, 1));
        }
        prev = node;
      }
    }

Is it just a fluke that the second block of code does what it is supposed to, but the first does not?

You should probably consider using something something like the "tortoise and the hare" algorithm, see [wikipedia](http://en.wikipedia.org/wiki/Cycle_detection). — Mankarse, Nov 02 '12 at 01:53
ahh yeah the floyd warshall algorithm. forgot about that. why is my lookup table idea stupid? just wondering for learning purposes — ordinary, Nov 02 '12 at 01:54
As for the "wtf", [find](http://en.cppreference.com/w/cpp/container/map/find) returns an iterator to the element that it finds, or the "one-past-the-end" iterator if it does not find any element. You are dereferencing this iterator, so your code has undefined behaviour. — Mankarse, Nov 02 '12 at 01:54
right. but that brings up more questions. specifically, when I say find(node) != map::end --- the compiler complains that I'm using std::map without template parameters. also, why would the second function that I included work perfectly, using almost exactly the same technique. Is that just luck? — ordinary, Nov 02 '12 at 01:58
"I tried doing this with std::set but it gave me trouble, so I switched to map." - why not ask a question about the trouble you had with `set`, documenting exactly what the trouble was? - there's no reason to use a `map`. BTW - that "remove duplicates" function is completely broken and has undefined behaviour - dereferencing `end()` for not-yet-seen nodes - I can't imagine it "works" in even the best of circumstances. — Tony Delroy, Nov 02 '12 at 02:34
I think the trouble was that I was trying to use set::end to find if the element was in the set, but I should have been using {name of set object}.end() — ordinary, Nov 02 '12 at 02:59

score 2 · Answer 1 · answered Nov 02 '12 at 02:01

You need to check if the find operation actually finds the data

auto iterator itr = address.find(node);
if(itr != address.end()){
    if(itr->second == true){ cout << "WTF" << endl; }
}

similar for the while loop. As for your approach, I think it has the best runtime possible of O(n). All you can do is lower the constant.

score 1 · Answer 2 · answered Nov 02 '12 at 02:02

1

addresses.find(node)->second

currently produces undefined behavior when the find() fails, because you're trying to access the second field of a past-the-end iterator. Instead, use

addresses.find(node) != addresses.end()

Also: is it important to find the exact place where a cycle (that's what it's usually called), or do you just want to see whether a cycle exists or not? If yes latter, then an extremely clever algorithm can solve the problem in linear time and constant space using just two pointers, one of which moves twice as fast as the other :)

answered Nov 02 '12 at 02:02

j_random_hacker

50,331
10
105
169

ahhhh thank you!! the addresses.end() was what I needed. As for your question, I need to return the node where the cycle starts. But the solution in the book is the two-pointer solution, so it must work in that case – ordinary Nov 02 '12 at 02:08
The tortoise and hare algorithm does not in general find the node where the cycle *starts* -- all it guarantees is that it will find *a* node if there is a cycle. – j_random_hacker Nov 02 '12 at 02:13
I don't understand how it will know if there is a cycle or not. What indicates that there is a cycle when you increment one pointer by one and another by two? – ordinary Nov 02 '12 at 02:16
@ordinary: The best explanation I have found of the tortoise-and-hare algorithm is by templatetypdef, here: http://stackoverflow.com/a/5130334/47984. Hope that helps! – j_random_hacker Nov 02 '12 at 13:55

Finding a circle in a linked list with lookup table

2 Answers2