C++单链表删除值为0的节点实现求助

问题描述 #

输入链表|1|3|0|4|0|5|0|0|，处理后需得到|1|3|4|5|，原代码中delete_value_0函数存在逻辑缺陷：添加break时仅删除第一个0就终止遍历；去掉break则程序陷入死循环，注释首尾节点删除逻辑后仍无法解决。

原函数核心问题 #

• 未处理头节点值为0的场景，直接跳过了头节点的检查
• 删除节点后未正确控制指针移动，导致重复检查同一位置引发死循环
• 刻意规避尾节点的删除逻辑，导致尾部的0无法被清理
• 未处理连续多个0的情况，删除单个0后没有继续检查当前位置的后续节点

修正后的完整代码 #

#include <iostream>
#include <fstream>

using namespace std;

struct node {
    int data;
    node* next;
};
node* head, *last;
int n;

void creating_list()
{
    node* aux;
    ifstream f("in.txt");
    f >> n;
    // 初始化指针，避免野指针风险
    head = last = NULL;
    for(int i=0;i<n;i++)
    {
        if (head == NULL)
        {
            head = new node;
            f >> head->data;
            head->next = NULL;
            last = head;
        }
        else
        {
            aux = new node;
            f >> aux->data;
            last->next = aux;
            aux->next = NULL;
            last = aux;
            
        }
    }
}

void displaying_list() 
{
    node* a;
    a = head;
    if (a == NULL)
        cout << "List is empty! ";
    else
    {
        cout << "| ";
        while (a)
        {
            cout << a->data<<" | ";
            a = a->next;
        }
    }
    cout << endl;
}

void delete_first_node()
{
    if (head == NULL)
        cout << "List is empty";
    else
    {
        node* aux = head;
        head = head->next;
        // 删除后链表为空时同步更新last
        if (head == NULL)
            last = NULL;
        delete aux;
    }
}

void delete_last_node()
{
    if (head == NULL)
        cout << "List is empty";
    else
    {
        if (head == last)
        {
            delete head;
            head = last = NULL;
        }
        else
        {
            node* current = head;
            while (current->next != last)
                current = current->next;
            delete current->next;
            current->next = NULL;
            last = current;
        }
    }
}

void delete_value_0()
{
    if (head == NULL)
    {
        cout << "List is empty. Can't delete! ";
        return;
    }

    // 循环处理所有头节点为0的情况
    while (head != NULL && head->data == 0)
    {
        delete_first_node();
    }

    // 处理后头节点为空则直接返回
    if (head == NULL)
        return;

    node* current = head;
    // 遍历链表，检查当前节点的下一个节点
    while (current->next != NULL)
    {
        if (current->next->data == 0)
        {
            node* toDelete = current->next;
            // 删除尾节点时同步更新last指针
            if (toDelete == last)
            {
                last = current;
                current->next = NULL;
            }
            else
            {
                current->next = current->next->next;
            }
            delete toDelete;
            // 删除后不移动current，新的next可能仍是0
        }
        else
        {
            // 下一个节点非0时才移动指针
            current = current->next;
        }
    }
}

int main()
{
    creating_list();
    cout << "原链表：";
    displaying_list();
    
    delete_value_0();
    
    cout << "处理后链表：";
    displaying_list();
    
    return 0;
}

修正说明 #

1. 指针初始化：在creating_list中显式初始化head和last为NULL，避免野指针风险
2. 头节点处理：循环删除所有值为0的头节点，确保链表开头无0
3. 遍历逻辑优化：删除节点后不移动current指针，继续检查新的next节点，解决连续0的问题；仅当下一个节点非0时才移动指针，避免死循环
4. 尾节点维护：删除尾节点时同步更新全局last指针，保证链表状态一致
5. 边界判断：处理完头节点后若链表为空，直接返回，避免后续空指针访问

内容的提问来源于stack exchange，提问作者BagPulaInEaProgramareNuInteleg