leetcode203.移除链表元素

题目

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == 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
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

解答

1. 虚拟头节点法：

若使用常规思路，在移除节点有两种情况：

• 非头节点的移除：直接讲被删除节点的前一个节点同被删除节点的后一个节点连接，然后删除当前的被删除节点；

• 头节点的移除：新建一个节点指向头节点，令头节点等于头节点的后继节点，然后删除刚才指向头节点的新建节点。

为了防止需要写两个逻辑判断到底怎么删除节点，在这里直接使用一个虚拟节点，他的后继节点指向头节点，此时本来需要被特殊处理的头节点也可以按照非头节点的移除方法进行移除了，在循环的最后删除虚拟头节点，返回虚拟头节点的后继节点（即真实头节点）。C++代码实现思路如下：

/**
 * 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* visualHead = new ListNode(0); // 新建虚拟头节点
        visualHead->next = head;
        ListNode* cur = visualHead; // cur指现在要处理的节点，默认指向虚拟头节点
        while (cur->next!=NULL) { // 开始循环
            if (cur->next->val == val) { // 如果值匹配，则进行删除
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else { // 否则当前指针更新为它的next指针指向的元素
                cur = cur->next;
            }
        }
        head = visualHead->next; // 得到删除对应元素之后的头节点
        delete visualHead; // 删除虚拟头节点，以降低空间复杂度
        return head; // 返回头节点，算法结束
    }
};