在本篇文章中，我们将深入探讨 LeetCode 题目 "203. 移除链表元素" 的解题方法，从问题的分析、解题思路、代码实现到核心知识点的罗列，带你逐步理解如何使用C++来删除链表中所有满足指定值的节点，并返回新的头节点。
题目分析
题目要求我们删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。我们需要对链表进行遍历，删除满足条件的节点，然后返回新的头节点。这涉及到链表操作和指针的使用，同时要求我们在原地修改链表，不使用额外的数组空间。
解题思路
我们可以使用双指针方法来解决这个问题。一个指针用于遍历链表，另一个指针用于指向当前有效的节点。当遍历到的节点值等于给定的 val 时，我们将当前有效节点的 next 指针指向下一个节点，从而实现删除操作。这样，我们可以在一次遍历中删除所有满足条件的节点，达到题目要求。
代码实现
以下是使用 C++ 实现的代码示例：
#include <iostream> struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode dummy(0); // 创建虚拟头节点 dummy.next = head; ListNode *prev = &dummy; // 指向当前有效节点的指针 ListNode *curr = head; // 用于遍历链表的指针 while (curr) { if (curr->val == val) { prev->next = curr->next; // 删除当前节点 } else { prev = prev->next; // 移动指针到下一个有效节点 } curr = curr->next; // 继续遍历 } return dummy.next; // 返回新的头节点 } }; int main() { Solution solution; // 创建链表: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 ListNode *head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(6); head->next->next->next = new ListNode(3); head->next->next->next->next = new ListNode(4); head->next->next->next->next->next = new ListNode(5); head->next->next->next->next->next->next = new ListNode(6); int val = 6; ListNode *newHead = solution.removeElements(head, val); // 输出删除后的链表: 1 -> 2 -> 3 -> 4 -> 5 ListNode *curr = newHead; while (curr) { std::cout << curr->val << " "; curr = curr->next; } return 0; }
代码解析
- 我们使用了一个虚拟头节点 dummy 来简化链表的操作，避免处理头节点的特殊情况。
- 使用两个指针 prev 和 curr 分别表示当前有效节点和遍历指针。
- 我们遍历链表，判断当前节点的值是否等于给定的 val，如果相等，则删除当前节点，即将前一个节点的 next 指针指向当前节点的下一个节点。
- 如果不相等，我们将 prev 指针移动到下一个有效节点。
- 最后，返回虚拟头节点的 next 指针，即新的头节点。
知识点罗列
- 链表的遍历和操作
- 指针的使用和操作
- 虚拟头节点的概念和作用
总结
通过解决 "203. 移除链表元素" 题目，我们深入理解了如何使用双指针方法删除链表中满足条件的节点，并返回新的头节点。在这个过程中，我们学习了链表的遍历和操作，以及指针的使用。同时，通过虚拟头节点的引入，使得链表操作更加简化，不需要额外处理头节点的特殊情况。这一题目的解答也加强了我们对于链表这种常见数据结构的理解和应用能力，为我们更深入的算法和数据结构学习奠定了基础。
首先，我们从问题背景入手，了解题目的要求和限制条件。题目中给出一个链表的头节点 head 和一个整数 val，要求我们删除链表中所有值等于 val 的节点，并返回新的头节点。通过理解题目描述，我们对问题的情景和目标有了清晰的认识，为后续的解题思路做好了准备。
接着，我们详细讨论了解题思路。在链表操作中，删除节点通常需要考虑头节点和非头节点的情况。具体而言，我们可以使用双指针方法，一个指针用于遍历链表，另一个指针用于指向当前有效的节点。当遍历到的节点值等于 val 时，我们将当前有效节点的 next 指针指向下一个节点，从而实现了删除操作。通过这一方法，我们可以在一次遍历中删除所有值等于 val 的节点，从而达到题目要求。这一解题思路的提出，使得问题的复杂性得到了降低，解题过程更加清晰。
随后，我们进行了代码实现。通过使用 C++ 编程语言，我们将解题思路转化为具体的代码逻辑。在代码实现过程中，我们首先处理了头节点为空的特殊情况。然后，我们使用两个指针，一个指针遍历链表，另一个指针指向当前有效节点。在遍历过程中，我们通过判断节点值是否等于 val，来决定是否删除节点。这一代码实现的过程，将解题思路具体化为计算机指令，实现了链表的删除操作。
