移出链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

移出思路

方法一：设置头节点使得移出操作统一化

• 循环条件：当cur->next不为空时寻找del的目标
• 删除要使用delete
• ListNode是要给出指针才能实例化，或者使用；

方法二：不使用头节点

• case1:考虑一直在头节点删除的情况，只有在头节点不为空，且头节点是val的情况下实现。头节点后移之前，需要del指向该节点，而后delete删除。
• case2:要注意输入就是空节点的情况，要确定不会使用空指针

代码

Java

这里我们手动将移除的节点置空，以便快速加快gc；

/**
 * Definition for singly-linked list.
 */
class ListNode {

    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {

    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0, head);
        ListNode cur = dummyHead;
        while(cur != null && cur.next != null){
            if(cur.next.val == val){
                ListNode del = cur.next;
                cur.next = del.next;
                del = null;
            }else{
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }
}

Cpp

方法一

[[include]] <iostream>
[[include]] <vector>
using namespace std;

// 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)
    {
        if (head == nullptr)
            return nullptr;
        ListNode *fast = head, *slow;
        ListNode *Head = new ListNode(0, head);
        slow = Head;
        while (fast)
        {
            if (fast->val != val)
            {
                fast = fast->next;
                slow = slow->next;
            }
            else
            {
                ListNode *del = fast;
                fast = fast->next;
                slow->next = fast;
                delete del;
            }
        }
        return Head->next;
    }
};

int main()
{
    ListNode *head = new ListNode(1);
    ListNode *p = head;
    p->next = new ListNode(2);
    p = p->next;
    p->next = new ListNode(6);
    p = p->next;
    p->next = new ListNode(3);
    p = p->next;
    p->next = new ListNode(4);
    p = p->next;
    p->next = new ListNode(5);
    p = p->next;
    p->next = new ListNode(6);
    Solution s;
    ListNode *res = s.removeElements(head, 6);
    while (res)
    {
        cout << res->val << " ";
        res = res->next;
    }
    return 0;
}

方法二

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* cur = head;
        ListNode* del = new ListNode();
        while (head && head->val == val) {
            del = head;
            head = head->next;
            delete del;
        }
        cur = head;
        while (cur && cur->next) { //要保证cur也不为空
            if (cur->next->val == val) {
                del = cur->next;
                cur->next = cur->next->next;
                delete del;
            } else
                cur = cur->next;
        }
        return head;
    }
};