203. 移除链表元素

题目：https://leetcode-cn.com/problems/remove-linked-list-elements/

循环

循环应该是最容易想出来的，遍历链表中的所有链表节点，找出与 val 值相同的节点然后将节点删除。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
  let prev = null;
  let current = head;
  while (current) {
    if (current.val === val) {
      if (current === head) {
        const next = current.next;
        head = next;
        current.next = null;
        current = next;
      } else {
        const tmp = current;
        prev.next = current.next;
        current = current.next;
        tmp.next = null;
      }
    } else {
      prev = current;
      current = current.next;
    }
  }
  return head;
};

从上面的题解中，是需要对头节点进行单独的处理的，为了避免单独处理的问题，我们使用虚拟头节点的方式：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummyHead = new ListNode(0);
  dummyHead.next = head;
  let prev = dummyHead;
  let current = dummyHead.next;
  while (current) {
    if (current.val === val) {
      const delNode = current;
      prev.next = current = delNode.next;
      delNode.next = null;
    } else {
      prev = current;
      current = current.next;
    }
  }
  return dummyHead.next;
};

递归

思路：链表具有天然的递归性。对于链表来说，我们可以理解为一个一个节点的连接，也可以理解为一个节点链接又连接了一个更短的链表，以此类推。因此链表中的很多操作都可以通过链表来完成。

我们回到删除链表元素的问题上，当我们将链表分解为一个节点加上一个更短的链表之后，我们需要判断的就是头节点是否需要被删除。这对更短的链表也是一样的，我们判断一个更短的链表的头节点是否需要会被删除。

function removeElements(head: ListNode | null, val: number): ListNode | null {
  if (head === null) {
    return null;
  }
  const head.next = removeElements(head.next, val);
  head.val === val ? head.next : head;
};