c++ - 使用查找表在链表中查找圆圈

Question

我试图在链表中找到一个圆，并返回圆开头的节点。例如，如果列表是 A -> B -> C -> D -> C —— 我们将返回 C

这是我的代码:

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;

}

我有几个问题:

1) 这是解决问题的正确方法吗

2) 我是否使用了最有效的方法来查找/插入键和值到表中

3) 为什么它不起作用？当我检查 head 的 map 时，在我插入 head 之前，它仍然执行该 if 语句并打印“wtf”。我的算法是，如果在映射中找不到该节点，则将该节点作为具有真值的键插入，否则如果该键已在映射中，则返回该节点。

我试着用 std::set 来做这件事，但它给我带来了麻烦，所以我切换到 map 。令我困惑的是，以下代码使用完全相同的方法工作(使用查找表删除链接列表中的重复项的代码)。

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

第二个代码块做了它应该做的，而第一个代码块没有做，这只是侥幸吗？

Answer 1

您需要检查查找操作是否确实找到了数据

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

类似于 while 循环。至于您的方法，我认为它具有 O(n) 的最佳运行时间。您所能做的就是降低常量。