C++面试(5)-----删除链表中指定值的节点

• 操作系统：ubuntu22.04
• IDE:Visual Studio Code
• 编程语言：C++11

算法描述

给定一个单向链表的头节点 head 和一个特定值 val，要求编写一个函数来删除链表中所有值等于 val 的节点，并返回修改后的链表头节点。
示例：

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解决方案

#include <iostream>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x), next(nullptr){}
};

void removeElements(ListNode* head, int val)
{
    while (head != nullptr && head->val == val)
    {
        ListNode *tmp = head;
        head = head->next;
        delete tmp;
    }

    if(head ==nullptr)
    {
        return;
    }

    ListNode *Cur = head;

    while(Cur->next != nullptr)
    {
        if(Cur->next->val == val)
        {
            ListNode* tmp = Cur->next;
            Cur->next = Cur->next->next;
            delete tmp;
        } 
        else
        {
            Cur = Cur->next;
        }  
    }
}

void printList(ListNode *head)
{
    while(head != nullptr)
    {
        std::cout << head->val;
        head = head->next;
    } 
}
int main()
{
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(6);


    removeElements(head, 6);
    printList(head);
}

运行结果

12345

注意事项

• 处理头节点：首先检查并处理头节点是否为要删除的目标值，因为头节点没有前驱节点。
• 遍历链表：对于每个节点，检查其下一个节点的值是否为目标值。如果是，则跳过该节点（即改变当前节点的 next 指针指向下一个节点的下一个节点）。
• 内存管理：每次删除节点时，记得释放被删除节点占用的内存，避免内存泄漏。