LinkedList在面试中使用

Question

[ 编辑 ]修正了我的代码.是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的测试

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"元素.实际上,有时以这种方式执行实现列表可能是有意义的.但我看到你的帖子中没有说明的内容.他们是否告诉过你这样对待它？

Answer 2

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

你可以简单地做

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

此外，正如WhozCraig 指出的那样，您的代码在逻辑上是错误的（以一分之差结束），而不仅仅是潜在的低效。