如何从单链表中删除偶数节点

Question

所以我的任务是采用预先编写的代码 generates/populates/prints/ 破坏单链表并添加计算偶数节点的函数。

指定原型为

int countEven(node * head)
计算并 return 线性链表中的节点数

 int removeEven(node *& head)
删除线性链表中所有包含偶数的节点和return删除的节点数

countEven 没有问题并且运行正常，但是 removeEven 似乎对随机数有效

例如，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;
}

函数 removeEven 看起来像这样...

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

这是我遵循的指导原则的一个例子，正确的多于错误的："when something looks too complicated, it's probably quite buggy"。

只要方法正确，这应该不会很复杂。

不管你信不信，正确的做法不是尝试保留指向当前被检查元素的指针，而是保留指向当前元素指针的指针，原因显而易见：

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;
}

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

如何从单链表中删除偶数节点

How to remove Even numbered nodes from a singly linked list

c++

linked-list

nodes

delete-operator