递归查找链表中的奇偶数？

Question

祝大家新年快乐！:)

我可以在一年的第一天做更好的事情，但我试图同时实现链表和递归。

我只是在想如何写一个递归计算链表中偶数的函数。

void List:: findingEvens(Node* n, Node*& newHead){
    if(n  == NULL)
        return;
    else
        if(n-> data % 2 != 0)
            findingEvens(n-> next);
    else{
        if(!newHead){
            newHead = n;
        }
        else{
             Node* temp =head;
             for(;temp->next;temp=temp->next){
                temp = temp -> next;
              }
             temp-> next = n;
             findingEvents(n-> next);
        }
    }  
}

问题是我在h类中按原样添加了以下内容

void findingEvens(Node* n);

然而，这使我出错，错误是：‘Node’没有声明，实际上我在h类中定义了这个函数之后有一个Node结构。

递归函数的实现是错误的吗？感谢您的帮助，再次祝您新年快乐:)

Answer 1

void List:: findingEvens(Node* n, Node*& newHead){
    if(n  == NULL)
        return;
    else
        if(n-> data % 2 != 0)
            findingEvens(n-> next, newHead);
    else{
        // Push even node onto newHead list
        newNode = new Node;
        newNode->data = n->data;
        newNode->next = newHead;
        newHead = newNode;
        findingEvens(n-> next, newHead);
    }
}

您需要在递归调用中传递newHead。

您不能直接将n赋值给newHead，因为这样newHead列表将拥有原始列表中的所有链接。您需要创建新节点并复制数据。

上面的代码以与原始列表相反的顺序构建结果列表，例如，如果你从1, 2, 3, 5, 6, 8, 9开始，结果将是8, 6, 2。完成后，您可以反转列表。