Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

203. Remove linked list elements

Val == val; delete all nodes in the list where node. val == val and return the new head Node.

 

Example 1:

Input: the head =,2,6,3,4,5,6 [1], val = 6 output: [1, 2, 3, 4, 5]Copy the code

Example 2:

Input: head = [], val = 1Copy the code

Example 3:

Input: head = [7,7,7], val = 7Copy the code

The problem solving method

There are two ways to manipulate linked lists:

  • Delete directly using the original linked list
  • Set a virtual head node and delete it

The virtual head node is not set

/** * 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) {
        // delete the header node
        while(head ! =NULL && head->val == val)
        {
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
        }

        // delete other nodes (not the head node)
        ListNode *cur = head;
        // non-head node, cur initially points to the head node, so find if the value of the node after cur is val
        while(cur ! =NULL&& cur->next ! =NULL)
        {
            if (cur->next->val == val)
            {
                ListNode *tmp = cur->next;
                cur->next = cur->next -> next;
                delete tmp;
            }
            else
            {
                // Find the node backwardscur = cur->next; }}returnhead; }};Copy the code

Set the virtual head node

/** * 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) {
        // Set up a virtual head node
        ListNode *dummyHead = new ListNode(0);
        // Place the next pointer to the virtual head node at head for later operations
        dummyHead->next = head;
        // Set the current node to point to the virtual head node
        ListNode *cur = dummyHead;
        while(cur->next ! =NULL)
        {
            // If the value of the next node of the current node equals the value to be deleted
            if (cur->next->val == val)
            {
                // Record the node to be deleted
                ListNode *tmp = cur->next;
                // Reset the link
                cur->next = cur->next->next;
                // Delete a node
                delete tmp;
            }
            else
            {
                // Continue looking backwards for the node
                cur = cur->next;
            }
        }

        head = dummyHead->next;
        delete dummyHead;
        returnhead; }};Copy the code

[Ref] : Code catalog