链表中的递归长度函数实现

Question

我正在实现一个链表，其中一个函数询问链表中的节点数。但是，正如要求所说，它需要递归完成。

这是我到目前为止的实现。

class  LList {
public:
bool isEmpty() const;
void cons(int x);
int length() const;
private:
struct Node {
int item;
Node* next;
};
Node* head;
}
bool LList::isEmpty() const{
if(head == nullptr)
return true;
else
return false;
}
void LList::cons(int x){
Node* temp = new Node;
temp->item = x;
temp->next = head;
head = temp;
}

我只能迭代地执行此操作，但无法使递归工作。

int LList::length(Node* head) const{
Node* temp = head;
if (temp == nullptr) {
return 0;
}
return 1 + length(temp->next);
}
int LList::length() const {
return length(head);
}

我尝试使用帮助程序函数来完成这项工作，但它说声明与int LList::length() const不兼容

谁能帮我解决这个问题？

Answer 1

你递归的地方是错误的：你只有一个LList，所以那里没有什么可递归的。相反，您要做的是在Node对象上递归。

保留你的int LList::length() const函数，但它所要做的就是检查head是否nullptr，然后调用你将要制作的新递归函数：int LList::Node::length() const。然后，这个递归于Node对象的next指针并对其进行计数。