1

我试图在链表中找到一个圆圈，并返回圆圈开头的节点。例如，如果列表是 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 时，在我插入 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;
      }
    }

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

4

2 回答 2

2

您需要检查 find 操作是否真的找到了数据

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

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

于 2012-11-02T02:01:46.550 回答
1 
addresses.find(node)->second

当前在find()失败时会产生未定义的行为，因为您正在尝试访问second结束迭代器的字段。相反，使用

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

另外：找到一个循环的确切位置是否重要（这就是它通常所说的），或者你只是想看看一个循环是否存在？如果是后者，那么一个非常聪明的算法可以仅使用两个指针在线性时间和恒定空间中解决问题，其中一个指针的移动速度是另一个指针的两倍 :)

于 2012-11-02T02:02:17.653 回答