【LC203】链表删除元素

题目链接：https://leetcode-cn.com/problems/remove-linked-list-elements/submissions/

题目描述：输入一个值val，删除给定链表里所有值为val的节点

输入: 1->2->6->3->4->5->6, val = 6. 输出: 1->2->3->4->5

---

思路解析：
通过遍历整个链表来删除元素，通过next指针跳过当前节点指向下一个节点来完成对当前节点的删除。这里的难点在于：你需要知道i-1节点的next指针，和i+1的地址，这样才能对i节点进行“绕过删除”。这样一来，你可以在头节点前再加一个临时节点来完成位置"+1"，即处理第i个节点的时候，查验第i+1个节点的val，如果第i+1个节点符合被删除条件，则直接让i节点的next指针指向i+2节点的地址。

---

cpp代码：

/**
 * 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 x;
        x.next = head;
        ListNode *p = &x;
        while(p->next){
            if(p->next->val == val){
                p->next = p->next->next;
            }
            else{
                p = p->next;
            }
        }
        return x.next;
    }
};

LC 运行效率