leetcode203

题目

203 移除链表元素
题意：删除链表中等于给定值 val 的所有节点。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

思路

本题很简单，就是遍历链表查找相等的节点并删除。唯一需要注意的是对head节点的处理。
我们使用虚拟头节点法，保证头节点的删除和中间节点的删除保持一致：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *removeElements(ListNode *head, int val)
    {
        ListNode *tmpHead = new ListNode(0, head); //虚拟头节点
        ListNode *index = tmpHead;
        while (index->next != nullptr)
        {
            //当前节点有可能是虚拟头节点，所以直接判断下一节点值，并删除
            if (index->next->val == val)
            {
                ListNode *tmp = index->next;
                index->next = index->next->next;
                delete tmp;
            }
            else
            {
                index = index->next;
            }
        }
        head = tmpHead->next;
        delete tmpHead;
        return head;
    }
};