/**
* 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) {}
* };
*/
// 没用虚拟头节点的解法，[7 7 7 7][7]解决不了，因为要删除head 7，这个方法删不掉。
// 因为一上来就从cur->next（即head->next，第二个node）开始判断了。所以要用到虚拟头节点。
/* class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* cur = head;
while (cur) {
if (cur->next == nullptr) {
break;
}
cout<<cur->val<<endl;
while (cur->next && cur->next->val == val) {
ListNode* del_node = cur->next;
cur->next = cur->next->next;
delete del_node;
}
cur = cur->next;
}
return head;
}
}; */
// 复习
// 此题是链表的典型题目之一，移除指定的链表元素，需要用到虚拟头节点dummy_node。
// 首先拿到题，思考大概脉络。需要遍历链表while(cur), cur=cur->next是跑不掉的，然后遍历过程中，如果遇到
// val满足要求的就删掉。那么删掉又是一个关键点，链表node的删除其实也比较容易，2>6>3变成2>3，其实只需要把
// node 3的地址给node 2的next就好了，怎么做呢？如果cur指向node 6，cur->next就是node 3的地址，但node 2
// 就没法访问了（单向链表没法往前访问），所以cur只能指向node 2，那这个过程就是cur->next=cur->next->next。
// 这里就是本题的关键因素之一了！那判断val值也就成了：if(cur->next->val==val)。此时大概有了思路，但要注意
// cur->next的提前判空null等有效边界问题，此时不用细想，但要大概有数。
// 然后这题要用dummy_node，原因已经在上面解释了。如果不用，做着做着就会发现，if(cur->next->val==val)，如果
// cur=head从第一个node起，则上来就把head的判断给跳过了，如果head->val==val，要删head就做不到了，所以想到
// 使用dummy_node，删除head和其他后面node一视同仁。
// dummy_node是在head前，纯新new ListNode()得到的一个node实例，dummy_node指针指向这个node实例，其val=0，
// 其next=head，其实可以理解为，dummy_node和head都一个性质，都是ListNode*指针，只不过一个指向虚拟node，
// 一个指向正式的第一个node，且一般都不能用于移动（我们通常用cur这个ListNode*来移动遍历）。有了dummy_node
// 后，cur也是必不可少的，那么此时访问head，就用cur->next就好了。
// 以示例1为例子：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
// 遍历整个链表时，我们仍然直接考虑while(cur)来做循环往前，因为cur一般都是有走到尾后null的可能的，那么这么
// 判断一般没问题。那此时需不需要写成while(cur->next)或while(cur&&cur->next)的形式呢？可以首先不用，因为
// 虽然看似有虚拟头节点，我们主要是基于cur->next而不是cur玩，但整个遍历过程仍是以while(cur),cur=cur->next
// 为核心的，如果后续有需求，在考虑加上while(cur->next)等判空也不迟。
// 开始说到，核心逻辑是if(cur->next->val==val),cur->next=cur->next->next。这里有几点需要注意一下。首先就
// 这个代码的理解。对于2>6>3，cur指向node 2，则cur->next就是node 2的next指针，此时也就是node 6的地址，而
// cur->next->val自然就是node 6的val，其实也就是6，判断和target相等，所以cur->next，也就是node 2的next
// 指针，重新赋值为cur->next->next，拆解一下，cur->next就是node 2的next指针，此时装的node 6的地址，那后面
// 再跟(cur->next)->next，也是访问node 6的next指针，此时装的就是node 3的地址。因为，就是把node 3的地址
// 重新给到了node 2的next指针，从而让node 2指向了node 3，抛弃了node。
// 总结下，如何快速理解cur->next在“=”左边和右边？左边就是cur所在node的next指针，要重新赋值；右边就是取cur
// 所在node的next指针此时装的值，也就是此时cur的node所连的下个node的地址。
// 上述理清后，有个细节需要注意。我们node 6删除后，我们一般还可以将其手动delete掉，防止内存泄漏。如果直接
// delete cur->next显然不妥，毕竟后面还要用借node 6访问node 3，所以一般就先用del_node存好cur->next，将
// node 2>node 3后，再delete del_node即可。
// 在if(cur->next->val==val),cur->next=cur->next->next处理完成后，此时cur所在node 2指向的下个node，已经
// 从node 6更新成node 3了，所以我们直接让cur继续前进就好了，即cur=cur->next。注意，这步应该在if外面，因为
// 无论如何cur在每次while(cur)循环都会前进，之前也提到了while(cur),cur=cur->next是绑定的。
// 执行示例1正确，提交遇到错误示例[7 7 7][7]，虽然head的问题我们用dummy_node解决了，但此时的代码逻辑，
// 会删掉head（第一个node 7），然后让cur（此时的dummy_node）指向第二个node 7，也就是说有的node 7还是没
// 删掉，问题一看就出在if(cur->next->val==val)的if上，这种之前也总结了，如果要连续满足条件删除，那么应该
// 用while试试。如果是while(cur->next->val==val)的话，那么再推一遍逻辑：cur此时为dummy_node，cur->next
// ->val就是第一个node 7的值，进入条件删掉，然后cur的dummy_node的next重新赋值为第二个node 7的地址（即
// 指向第二个node 7）；再次判断while循环，发现cur->next->val即访问第二个node的值还是满足条件，则继续进入
// while，将第三个node的地址重新赋给cur的dummy_node的next指针（即指向第三个node 7）；再次判断while循环，
// 发现cur->next->val即访问第三个node的值还是满足条件，则继续进入while，将cur->next->next（cur->next为
// 第三个node 7的地址，再->next是第三个node 7的next指针内容，此时是null），然后将null重新赋给cur的
// dummy_node的next指针；再次判断while循环，此时注意，cur->next指针已经是null了，那再访问cur->next->val
// 就会报错，所以在while条件里再加上边界条件，就成了while (cur->next && cur->next->val == val)。
// 上述一大堆，有几个小点可以帮助我们快速反应：
// 1）cur这个ListNode*其实移动的，对cur本身的赋值，是让我们的cur可以移动附着到不同的node上，以便
// 操控该node的val值(cur->val)或者next指针(cur->next)。
// 2）cur->next这种写法，代表的是当前cur附着的node的next指针，=左边是为了赋值，=右边是为了取值，当前node
// 所连下个node的地址。这不是在移动cur，而是在操作cur当前附着指向的node的成员，val或next指针。
// 最后return谁呢？还是考虑之前那两个示例（别想太复杂，就直接考虑这俩示例，一个通用一个特殊，遇到问题再说）。
// 示例1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
// 遍历结束时，会发生什么？cur附着node 5时，满足内层while条件，然后让cur->next赋值为null，然后退出内层
// while，此时node 5指向了null，已经合格地把最后的node 6剔除了。然后cur=cur->next，cur前进到自己为null，
// 然后退出外层while。没问题，最后返回head也行，返回dummy_node->next也行，当然我们返回dummy_node->next。
// 示例特殊：[7 7 7 7][7]
// 遍历结束时，cur就一直附着在dummy_node没动，但cur->next指针此时赋值为null，然后退出内层while，然后
// cur=cur->next，cur自己移动到尾后null，整个链表还剩下，dummy_node直接连null。
// 所以也return dummy_node->next，也就是一个nullptr空指针，代表头节点为空，整个链表也不存在了。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// dummy_node模板：先new一个示例node(0, nullptr)。
ListNode* dummy_node = new ListNode();
// dummy_node模板：dummy_node的node的next指针赋值为头节点的地址，即dummy_node>head。
dummy_node->next = head;
// dummy_node模板：有dummy_node，cur此时就不附着于head，而附着于dummy_node。
ListNode* cur = dummy_node;
// 链表遍历模板：while(cur),cur=cur->next绑定。
while (cur) {
// log方便定位问题，不过这里会打出dummy_node，且不会打出删除的node。
// 因为打印的cur，而cur->next先处理了。
// cout<<cur->val<<endl;
// 从if(cur->next->val == val)到while(cur->next->val == val)。
// 最后到while (cur->next && cur->next->val == val)，心路历程的成长！
while (cur->next && cur->next->val == val) {
// delete node模板：核心是cur->next=cur->next->next。
// del_node先存起来在释放，是为了做得更好，避免内存泄漏。
ListNode* del_node = cur->next;
cur->next = cur->next->next;
delete del_node;
}
// 遍历遍历模板：while(cur),cur=cur->next绑定。
cur = cur->next;
}
// dummy_node模板：return不再是head，而是dummy_node->next。
// 我们认为，dummy_node后的第一个node，是新的头节点。
return dummy_node->next;
}
};
/**
* 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) {}
* };
*/
链表
无头节点：
ListNode* cur = head; // cur初始指向head
while (cur != nullptr) { // 当前node由cur表示，最后判空也是cur
...
cur = cur->next;
}
有头节点：
ListNode* dummy_head = new ListNode(0);
dummy_head->next = head;
ListNode* cur = dummy_head; // cur初始指向dummy_head，cur->next指向head
while (cur->next != nullptr) { // 当前node由cur->next表示，最后判空也是cur->next
...
cur = cur->next;
}
解法1：不采用虚拟头节点，考虑head和非head的情况。
思路：遍历删除链表元素，画出链表图，将指向需要删除的链表节点的指针(cur->next)指向下一个链表节点即可
(cur->next->next)，注意需要单独处理head指向的链表节点，因为(cur->next上来就跳过了head)。
注：核心是当遇到要删除的链表节点时，cur->next = cur->next->next;
注：C++没有内存回收机制，最好用tmp=cur->next，再delete tmp释放删除的链表；
注：特殊情况是头节点head需要单独处理，因为cur->next上来就跳过了head；
注：遍历过程用while，如果正常遍历++就cur = cur->next，如果删除就cur->next = cur->next->next，
用if-else来处理这段逻辑，因为正常遍历和删除都“往前走了一步”，属于while的一个步骤；
注：麻烦的点在于判空，一般需要考虑head、head->next、cur、cur->next!=nullptr，凭感觉先写出来，
然后带入推导看哪里有问题，具体情况再具体考虑；
注：当关注cur->val/next时，条件注意是cur!=nullptr。当关注cur->next->val/next时，条件注意是
cur->next!=nullptr。
1：head为空的情况后面已经考虑了，就不用再单独写。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// if (head == nullptr) return head; // wyh 1
while (head != nullptr && head->val == val) {
ListNode* tmp = head;
head = head->next;
delete tmp;
}
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};
解法2：采用虚拟头节点dummy_head。
思路：新增dummy_head虚拟头节点，指向head节点，然后只一个while循环解决完，因为此时第一个cur->next
就是head，不需要再单独处理head。
注：dummy_head的步骤比较关键，首先new()，然后连接head，然后赋值给cur。处理完成后，先用head接管
dummy_head->next，然后delete dummy_head，最后return head。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy_head = new ListNode(0);
dummy_head->next = head;
ListNode* cur = dummy_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;
}
}
head = dummy_head->next;
delete dummy_head;
return head;
}
};
