Linked list - 203. remove linked list elements

1 Title Description

203. Remove linked list elements
     Give you a list of the head node head And an integer val , Please delete all the contents in the linked list Node.val == val The node of , And back to New head node .

2 Title Example

Input ：head = [1,2,6,3,4,5,6], val = 6
Output ：[1,2,3,4,5]

Example 2：

Input ：head = [], val = 1
Output ：[]

Example 3：

Input ：head = [7,7,7,7], val = 7
Output ：[]

3 Topic tips

The number of nodes in the list is in the range [0, 104] Inside
1 <= Node.val <= 50
0 <= val <= 50

4 Ideas

To delete a node

1. Find the previous node of this node
2. Delete operation

Three methods

1. When deleting the head node, consider it separately （ Because the head node has no previous node ）
2. Add a virtual head node , There is no need to consider deleting the head node
3. recursive

5 My answer

Method 1 （ When deleting the head node, consider it separately ）

class Solution {
    
    public ListNode removeElements(ListNode head, int val) {
    
        // After deleting the head node with the same value , Maybe the new head node has the same value , Solve with circulation 
        while(head!=null&&head.val==val){
    
            head=head.next;
        }
        if(head==null)
            return head;
        ListNode prev=head;
        // Ensure that there are nodes after the current node 
        while(prev.next!=null){
    
            if(prev.next.val==val){
    
                prev.next=prev.next.next;
            }else{
    
                prev=prev.next;
            }
        }
        return head;
    }
}

Method 2 （ Add a virtual head node ）

class Solution {
    
    public ListNode removeElements(ListNode head, int val) {
    
        // Create a virtual header node 
        ListNode dummyNode=new ListNode(val-1);
        dummyNode.next=head;
        ListNode prev=dummyNode;
        // Ensure that there are nodes after the current node 
        while(prev.next!=null){
    
            if(prev.next.val==val){
    
                prev.next=prev.next.next;
            }else{
    
                prev=prev.next;
            }
        }
        return dummyNode.next;
    }
}

Method 3 （ recursive ）

class Solution {
    
    public ListNode removeElements(ListNode head, int val) {
    
       if(head==null)
           return null;
        head.next=removeElements(head.next,val);
        if(head.val==val){
    
            return head.next;
        }else{
    
            return head;
        }
    }
}

Talk about your understanding of recursive solution ： Recursive method is a stack pressing process , The recursive method is followed by a stack popping process . By constantly next, Traverse O(N) To the end of the linked list ; Then bounce stacks one by one to find matching values . Note that the return value of recursion in this solution is head.next, That is, the incoming next node ; If it matches, it returns the current node ; Mismatch , Back to head It's the previous node . When pressing the stack head.next For the next node ; When playing the stack head.next The previous node after positioning