The sample code in this article uses JavaScript

Zero, preface,

This paper is written for the algorithm xiaobai. We first analyze why the problem can be solved recursively, then disassemble the sub-problem and give the code, and use JavaScript to build a simple linked list to facilitate debugging. After this, the execution process of the code is analyzed in detail.

A, dry

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

Example 1:

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

Example 2:

Input: head = [], val = 1

Example 3:

Input: head = [7,7,7], val = 7

Second, the solution

If you want to use recursion to solve this problem, you need to understand the following two knowledge points

1. How to delete linked list nodes

First, we need to know how to remove nodes from a linked list. For non-headed nodes, the next pointer on the node before the deleted node points to next on its original next node, i.e., prev.next = prev.next-next. In the case of a header, we simply take the next node of the header, so that ignoring the header is equivalent to deleting it.

2. Recursive conditions

To determine whether a problem can be solved recursively, we need to see whether the problem meets the following three conditions.

  • The problem can be decomposed into several sub-problems
  • The idea of solving a subproblem is the same as the idea of solving this problem, but on a smaller scale
  • There are termination conditions, or recursive bases. (That is, the subproblem is small enough to be solved without further recursion)

Ideas:

Val == val = val = val = val = val = val = val = val = val = val = val = val = val = val 1 – > 2 – > 6 – > 3 – > 4 – > 5 – > 6, a value of 6, whether can be disassembled into 1 need to delete, and delete 6 – > 2 – > 3 – > 4 – > 5 – > 6 value is in the list of all nodes, 2->6->3->4->5->6 can be disintegrated into whether 2 needs to be deleted and delete the node with the value of 6 in the linked list 6->3->4->5->6, and so on until the last node. Because the next of the last node points to null, it can be used as the termination condition. It can be seen from the above analysis that the problem can be solved recursively.

The above ideas can be expressed in the following formula (only to express ideas = and + not in the mathematical sense) :

We can write the following code:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : Next) *} */ /** * @param {ListNode} head * @param {number} val * @return {ListNode} */ / build list const node3 = new ListNode(3, null) const node2 = new ListNode(6, node3) const node1 = new ListNode(2, Const head = new ListNode(1, node1) const head = new ListNode(1, node1) const head = new ListNode(1, node1) 1 let removeElements = function(head, val) { 2 if(head === null) { 3 return null 4 } 5 head.next = removeElements(head.next, val) 6 return head.val === val ? head.next : head 7 }; removeElements(head, 6)Copy the code

Review the code execution (linked list 1->2->6->3, val=6)

  • Head is 1 and removeElements is recursively executed
  • Head is 2 and removeElements is recursively executed
  • Head is 6 and removeElements is recursively executed
  • Head is 3, recursively executes removeElements (the code doesn’t get as far as line 6 so far)
  • Head is null and null is returned
  • Go back to the unexecuted code at the previous level, head is 3, head. Next is null, so after line 6, return 3
  • Go back to the code at the previous level, where head is 6 and head. Next is 3, so execute line 6 and return 3
  • Next is 3, so execute line 6 and return 2 (i.e., 2->3).
  • Next = 2->3, so execute line 6, return 1 (1->2->3)

Other methods

1. Special treatment of headers

let removeElements = function(head, val) { while(head && head.val === val) { head = head.next } if (! head) { return null } let pre = head while(pre.next) { if (pre.next.val === val) { pre.next = pre.next.next } else { pre  = pre.next } } return head };Copy the code

2. Add a dummy header

let removeElements = function(head, val) {
  const newHead = new ListNode(0, head)
  let pre = newHead
  while(pre && pre.next) {
    if (pre.next.val === val) {
      pre.next = pre.next.next
    } else {
      pre = pre.next
    }
  }
  return pre.next
};
Copy the code

Iv. Reference materials

  1. Ali Cloud developer community LeetCode 203: Remove linked list elements

LeetCode link: leetcode-cn.com/problems/re…

If you have any questions, please leave a message at ღ(´ ᴗ · ‘)