设计一个算法，删除单链表[1]L中第一个值为x 的节点。
设计一个算法，删除单链表[1]L中第一个值为x 的节点。
题目解答
答案
void deleteNode(ListNode* &head, int x) {
ListNode* p = head;
ListNode* pre = nullptr;
while (p != nullptr) {
if (p->val == x) {
if (pre == nullptr) {
head = head->next;
} else {
pre->next = p->next;
}
delete p;
break;
}
pre = p;
p = p->next;
}
}
其中 ListNode 是链表节点的结构体，包含一个整数 val 和一个指向下一个节点的指针 next。deleteNode 函数接受一个指向链表头节点的指针 head 和一个整数 x，并删除链表中第一个值为 x 的节点。
函数中使用两个指针 p 和 pre 分别指向当前遍历的节点和它的前驱节点。在遍历过程中，如果找到了值为 x 的节点，则按照上述步骤进行删除操作。如果没有找到值为 x 的节点，则不进行任何操作。需要注意的是，如果被删除的节点是链表头节点，则需要更新 head 指针的值。
解析
考查要点：本题主要考查单链表的基本操作——删除指定值的节点。需要掌握链表的遍历、前驱节点的处理、头节点的特殊性以及内存释放等知识点。
解题核心思路：
- 遍历链表：使用指针
p逐个访问节点，同时用pre记录当前节点的前驱。 - 判断节点值：若当前节点值等于
x，则根据pre是否为空判断是否为头节点，分别处理指针调整。 - 内存管理：删除节点后需释放内存，避免内存泄漏。
- 终止条件：找到并删除第一个符合条件的节点后立即终止遍历。
关键点：
- 头节点的特殊处理：若目标节点是头节点，需直接修改
head指针。 - 前驱节点的作用：通过
pre调整链表结构，断开目标节点。 - 指针操作的准确性：确保指针调整后链表仍保持有效结构。
算法步骤分解
1. 初始化指针
p指向头节点，用于遍历链表。pre初始为nullptr，表示当前节点的前驱。
2. 遍历链表
- 循环条件：
p != nullptr，即未遍历到链表末尾。 - 每次循环检查当前节点的值是否为
x：- 若找到目标节点：
- 判断是否为头节点：
- 若
pre == nullptr（即p是头节点），则将head指向p的下一个节点。 - 否则，将
pre的next指向p的下一个节点。
- 若
- 释放内存：
delete p。 - 终止循环：
break，确保只删除第一个匹配节点。
- 判断是否为头节点：
- 若未找到：更新
pre为当前节点p，并将p移动到下一个节点。
- 若找到目标节点：
3. 未找到目标节点的情况
- 若循环结束后未找到
val == x的节点，则不进行任何操作。