This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic Description:

203. Remove linked List elements – LeetCode (leetcode-cn.com)

Given a list with head and an integer val, remove all nodes in the list that satisfy node.val == val and return the new head Node.

The sample a

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,7], val = 7Copy the code

Tip:

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

Thought analysis

The steps to delete a node

  1. Find the node before this node
  2. Deleting a file

Three methods

  1. Think twice when deleting a head node (because the head node has no previous node)
  2. Add a virtual head node, and remove the head node without additional consideration
  3. recursive

The iteration

We choose to add a virtual node to point to the head node, and then iterate over the list.

Use temp to represent the current node. If the next node of temp is not empty and the node value of the next node is equal to the given val, the next node needs to be deleted.

If the node value of the next node of Temp is not equal to the given val, the next node is retained and temp is moved to the next node.

When the next node of Temp is empty, the list traversal ends, and all nodes whose value is equal to val are deleted.

AC code

class Solution {
    fun removeElements(head: ListNode? , `val` :Int): ListNode? {
        Dummy = next; dummy = next; dummy = next
        val dummy = ListNode(0)
        dummy.next = head
        var temp = dummy
        while(temp.next ! =null) {
            if (temp.next.`val` = = `val`) {
                temp.next = temp.next.next
            } else {
                temp = temp.next
            }
        }
        return dummy.next
    }
}
Copy the code

recursive

First, the node after the head node is deleted. Finally, the head node may need to be deleted, so it is processed separately

AC code

class Solution {
    fun removeElements(head: ListNode? , `val` :Int): ListNode? {
        vartemp = head temp? .next = removeElements(temp? .next, `val`)
        if(temp? . `val` = = `val`) {
            returntemp? .next }else {
            return temp
        }
    }
}
Copy the code

conclusion

It’s a very normal linked list operation

reference

Remove List Elements – Remove List Elements – Force link (LeetCode) (leetcode-cn.com)

203. Removing List Elements (Three Methods) – Removing List Elements – LeetCode (leetcode-cn.com)