6

[编辑]修复了我的代码。是 while(temp != NULL)，而不是 while(temp->next != NULL)。抱歉插入错误的代码。

今天我参加了一个在线编程测试。面试官使用 Codility 来评估我的代码和其他受访者。在某个时刻，有人提出了有关链接列表的问题。它即将计算一个链表有多少项。我做了唯一可能的方法来做到这一点，AFAIK：

//This is struct declaration
struct SomeStruct
{
    int value;
    SomeStruct* next;
}

int elementCount(SomeStruct* list)
{
    int count = 0;
    if(list != NULL)
    {
        SomeStruct* temp = list;
        while(temp != NULL)
        {
            count++;
            temp = temp->next;
        }
    }
    return count;
}

我记得当我发送这个代码作为这个问题的答案时，Codility 指出这个解决方案是错误的，因为它消耗了太多时间来执行任务。在我的脑海中，在这个关于 SO 的线程中，没有其他方法可以在不遍历链表的情况下获取链表的大小，而不是以简单的方式。

当 Codility 说此解决方案错误时，是否存在问题？还是有其他方法？

PS：允许使用STL的测试

4

3 回答 3

6

您的解决方案不正确，因为它返回的值比实际计数少 1。只需尝试将其应用于具有 1 个元素的列表即可。

你为什么想出这种奇怪的两层结构，其中一个if和一个循环检查temp->next？为什么不只是

unsigned elementCount(const SomeStruct *list)
{
  unsigned count = 0;
  for (const SomeStruct *temp = list; temp != NULL; temp = temp->next)
    ++count;
  return count;
}

我怀疑您决定将 指向的元素list视为未使用和保留的“标题”元素。事实上，有时以这种方式实现列表可能是有意义的。但我在你的帖子中没有看到任何类似的内容。他们有没有告诉你专门这样对待它？

于 2012-11-15T01:04:52.997 回答
3

好吧，您不必为每次迭代评估间接temp->next 两次。

你可以简单地做

int count( SomeStruct const* pNode )
{
    int result = 0;
    while( pNode != 0 )
    {
        ++result;
        pNode = pNode->next;
    }
    return result;
}

此外，正如WhozCraig 所指出的，您的代码在逻辑上是错误的（产生一个结果），而不仅仅是潜在的低效。

于 2012-11-15T01:01:13.910 回答
2

Codility 可能正在使用循环链表进行检查，在这种情况下，您的代码将永远不会结束。

不过，使用 STL 可以解决这个问题，因为它有一个带有 size 方法的 List<>。

于 2012-11-15T01:02:17.533 回答