如何从单向链表中删除偶数编号的节点

Question

所以我的任务是获取预先编写的代码来生成/填充/打印/销毁单向链表，并添加计算偶数个节点的函数。

指定的原型是

int countEven（node * head）
计算并返回线性链表中的节点数

 int removeEven（node *& head）
删除线性链表中包含偶数的所有节点，并返回删除的节点数

countEven不是问题并且运行正常，但是删除Even似乎适用于随机数

例如，main.cpp看起来像这样...

#include "list.h"
#include <iostream>
using namespace std;
int main()
{
node * head = NULL;
build(head);
display(head);
//PLEASE PUT YOUR CODE HERE to call the function assigned
cout << "The number of even nodes is " << countEven(head) << ".n";
cout << "The number of even nodes removed was " << removeEven(head) << ".n";
display(head);
destroy(head);
return 0;
}

和功能删除甚至看起来像这样...

int removeEven(node *& head)
{
    node *current;
    node *trailCurrent;
    int currentData = 0;
    int numberOfItemsRemoved = 0;
    current = head;
    trailCurrent = NULL;
    while(current != NULL)
    {
        currentData = current->data;        
        if(currentData % 2 == 0)
        {
            if (head == NULL)
            cout << "Cannot delete from an empty list.n";  
            else
            {
                if (head->data == currentData) //Node is in beginning of list
                {
                    current = head;
                    head = head->next;
                    delete current;
                    numberOfItemsRemoved++;
                }
                else
                {
                    trailCurrent->next = current->next;
                    delete current;
                    numberOfItemsRemoved++;
                }
            }
        }
        trailCurrent = current;
        current = current->next;
    }
return numberOfItemsRemoved;
}

输出是随机的，因为构建函数似乎用随机数制作随机列表，但这是一个示例

Here is the original list: 2 -> 51 -> 44 -> 46 -> 1 -> 49 -> 2 -> 53 -> 52 -> 2
This list contains 10 numbers of items
The number of even nodes is 6.
The number of even nodes removed was 6.

The resulting list is... 51 -> 31571024-> 1 -> 49 -> 53 -> 31571216
This list contains 6 number of items
The sum of all data is: 63142394

Valgrind 告诉我有大小为 8 的无效读取和写入，这告诉我某些东西正在写入或读取不应该的地方。我不认为头节点的情况是问题所在，因为随机数出现在列表中的第一个之后，在这种情况下，我认为删除功能会导致问题。谁能指出我哪里出错了？我检查了有关从列表中删除内容的其他条目，我的解决方案似乎没有错。感谢您的提示！

Answer 1

这是我遵循的指导原则的一个例子，它通常是对的而不是错的："当某件事看起来太复杂时，它可能很有问题"。

使用正确的方法，这应该不是很复杂。

不管你信不信，正确的方法不是试图保留指向当前正在检查的元素的指针，而是指向指向当前元素的指针的指针，原因应该很明显：

int removeEven(node *& head)
{
    node **currentptr= &head;
    int numberOfItemsRemoved = 0;
    while (*currentptr)
    {
        if ( (*currentptr)->data % 2)  // Odd
        {
            currentptr = &(*currentptr)->next;
            continue;
        }
        // Remove a node with an even value
        node *p= *currentptr;
        *currentptr= p->next;
        delete p;
        numberOfItemsRemoved++;
    }
    return numberOfItemsRemoved;
}

相当确定这将处理所有边缘情况。要删除多个连续节点，删除列表中的第一个节点，最后一个节点等...