Day 65/100 数据结构链表（6）——移除链表中的某个节点

（一）需求

今儿继续是链表结构的算法——移除链表中的某个节点

（二）移除链表中的某个节点

1、问题描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

Demo1:

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

Demo2:

输入：head = [], val = 1
输出：[]

Demo3:

输入：head = [7,7,7,7], val = 7
输出：[]

2、思路:

1. 定义一个头节点；
2. 迭代节点；
3. 判断值，如果值相等，那么把下一个节点的next赋值给当前节点的next值；

3、代码

/**
 * 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}
 */
var removeElements = function(head, val) {
  // 缺一个头节点，就定义一个
  let prev = new ListNode(0)
   // 便于处理，首节点的值就相同的情况
  prev.next = head
  let curr = prev // 重新定义一个头节点
  while(curr.next!=null){
    const next = curr.next // 下一个节点
    if (next.val == val){ // 下一个节点的值和目标值相等
      curr.next = next.next // 把下一个节点的next赋值给当前节点的next值
    }else{
      curr = curr.next
    }
  }
  return prev.next
};

空间复杂度将是 O(1)
时间复杂度将是 O(n)

以上

参考链接

https://leetcode.cn/leetbook/...

写在最后的话

学习路上，常常会懈怠

《有想学技术需要监督的同学嘛~》
https://mp.weixin.qq.com/s/Fy...