Linked list (I) - 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 .

Example ：

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

Tips ：

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

Ideas

iteration ( Non virtual node )

• Find the previous node of this node , Delete operation
• Removing the head node is different from removing other nodes
• Move the head node backward one bit to remove the node
• The head node is separated from other nodes
  

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;
    }
    //  Have been to null, Exit ahead of time 
    if (head == null) {
    
        return head;
    }
    //  Determined current head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
    
        if (cur.val == val) {
    
            pre.next = cur.next;
        } else {
    
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

iteration ( Virtual node )

• Add a virtual head node , There is no need to consider deleting the head node
  

public ListNode removeElements(ListNode head, int val) {
    
    if (head == null) {
    
        return head;
    }
    //  Because the deletion may involve the head node , So set dummy node , Unified operation 
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
    
        if (cur.val == val) {
    
            pre.next = cur.next;
        } else {
    
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}

recursive

• head It's empty , Go straight back to head
• When head Isn't empty , Delete recursively
• Judge head Whether the node value of is equal to val And decide whether to delete head

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;
        }
    }
}