如何在不遍历链表的情况下计算链表中的节点数? [英] How to count the number of nodes in a linked list without traversing it?

问题描述

我在面试中被问到如何在不遍历链表的情况下计算链表中的节点数?有什么办法可以做到这一点吗?

I have been asked in an interview how to count the number of nodes in a linked list without traversing the list? Is there any way to achieve this?

推荐答案

我能想到的唯一方法是添加一个节点数计数器，每次 add 或 insert 方法被调用，并在 delete 被调用时递减.你不能对内存占用做出假设，因为作为一个链表，你不能保证所有节点都在同一个内存块中(实际上，这是极不可能的).

The only way I can think of is to add a counter of the number of nodes which is incremented each time the add or insert methods are invoked, and decremented when delete is invoked. You cannot make assumptions about memory occupied because, being a linked list, you cannot guarantee that all nodes will be in the same memory block (indeed, this is highly improbable).

这篇关于如何在不遍历链表的情况下计算链表中的节点数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！