c++ - 面试测试中使用的LinkedList

Question

[EDIT]修复了我的代码。是 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 指出这个解决方案是错误的，因为它执行任务消耗了太多时间。在我的脑海和this thread因此，没有其他方法可以在不遍历链表的情况下获取链表的大小，这不是一种简单的方法。

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

PS:测试允许使用STL

Answer 1

您的解决方案不正确，因为它返回的结果比实际计数少 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 指向的元素视为未使用和保留的“header”元素。事实上，有时以这种方式实现列表可能是有意义的。但是我看不到您帖子中所说的任何内容。他们有没有专门告诉你要那样对待它？