This is the fourth day of my participation in the August Text Challenge.More challenges in August

Topic describes

Val == val; delete all nodes in the list where node. val == val and return the new head Node. The sample1: Enter: head = [1.2.6.3.4.5.6], val = 6Output:1.2.3.4.5] example2: Enter: head = [], val =1Output: [] Example3: Enter: head = [7.7.7.7], val = 7Output: [] Hint: The number of nodes in the list is in the range [0.104]1 <= Node.val <= 50
0 <= val <= 50Source: LeetCode//leetcode-cn.com/problems/remove-linked-list-elementsCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. The traversal

To delete an element from a linked list, make the previous node of the element to be deleted point to the next node of the element to be deleted

Val == val: delete all nodes where node. val == val.

Since this is a one-way linked list, we can only get the node after the current node, so we traverse the node before the node to be judged. But for the head node it does not have the previous element, so it needs special treatment

public ListNode removeElements1(ListNode head, int val) {
    // If the head node is empty, just return it
    if (head == null) {
        return head;
    }
    // Process the header node
    while (head.val == val) {
        head = head.next;
        if (head == null) {
            returnhead; }}// Iterate over the node after the first node
    ListNode cur = head;
    while(cur.next ! =null) {
        if (cur.next.val == val) {
            cur.next = cur.next.next;
        } else{ cur = cur.next; }}return head;
}
Copy the code

2. Add a virtual head node

It says that because there is no node before the head node, we need to do special treatment for the head node, but the code gets complicated because of this. So we can manually add a virtual head node to the list, so that each node in the list has a front node. Virtual header nodes are also a common technique for dealing with linked list problems

public ListNode removeElements2(ListNode head, int val) {
    ListNode dummyNode = new ListNode(-1, head);
    // The head node points to the virtual head node
    head = dummyNode;
    while(dummyNode.next ! =null) {
        if (dummyNode.next.val == val) {
            dummyNode.next = dummyNode.next.next;
        } else{ dummyNode = dummyNode.next; }}return head.next;
}
Copy the code

3. The recursion

I’ve written recursion code before, but the recursion here took me a long time to understand. For recursive algorithms, we write in two steps:

  1. Break down the current problem into smaller pieces until you can’t break it down
  2. Solve the smallest problem

Often, beginners write recursions thinking about how the code works recursively and end up getting caught up in it. We should be more concerned with the macro semantics of recursion and not the implementation details. Take a look at the following code

public ListNode removeElements3(ListNode head, int val) { if (head == null) { return head; } ListNode listNode = removeElements3(head.next, val); if (head.val == val) { return listNode; } else { head.next = listNode; return head; }}Copy the code

The first implication of this method is to remove specific values from the list and return the head node.

According to the solution steps, what is the smallest problem when the linked list is decomposed to the last, we use the traversal here, the smallest problem is that there is no element in the list, so the solution of the smallest problem is the head node to determine whether it is empty

if (head == null) {
    return head;
}
Copy the code

And then there’s how to break it down. We specifically emphasized the meaning of this method at the beginning: remove the specific value from the list and return to the head node, so we can simply call this method again. Pass head.next into this method, and the next thing to determine is the head node

  • If the head node is empty, simply return the node returned by the method
  • If the head node is not equal to a specific value, then connect the head node to the node returned by the method, returning the head node
ListNode listNode = removeElements3(head.next, val);
if (head.val == val) {
    return listNode;
} else {
    head.next = listNode;
    return head;
}
Copy the code

Of course, this method can also be simplified like this:

public ListNode removeElements4(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    head.next = removeElements4(head.next, val);
    return head.val == val ? head.next : head;
}
Copy the code