TNotes.leetcode

Appearance

0203. 移除链表元素【简单】

0203. 移除链表元素【简单】 ​

1. 📝 题目描述 ​

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

示例 1：

img

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

示例 2：

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

示例 3：

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

提示：

  • 列表中的节点数目在范围 [0, 10^4] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

2. 🎯 s.1 - 遍历 ​

js
/**
 * 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) {
  // 创建虚拟头节点，简化边界处理
  const dummy = new ListNode(0)
  dummy.next = head

  let prev = dummy
  let current = head

  while (current !== null) {
    if (current.val === val) {
      // 移除当前节点
      prev.next = current.next
    } else {
      // 移动 prev 指针
      prev = current
    }
    current = current.next
  }

  return dummy.next
}
  • 时间复杂度：O(n)，其中 n 是链表长度，需要遍历整个链表
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

算法思路：

  • 使用哨兵节点避免处理头节点删除的特殊情况
  • 遍历链表，如果下一个节点值等于 val，则跳过该节点；否则移动指针
  • 返回哨兵节点的 next

3. 🎯 s.2 - 递归 ​

js
/**
 * 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) {
  if (head === null) return head
  head.next = removeElements(head.next, val)
  return head.val === val ? head.next : head
}
  • 时间复杂度：O(n)，其中 n 是链表长度，需要递归访问每个节点
  • 空间复杂度：O(n)，递归调用栈的深度最多为 n

算法思路：

  • 递归处理链表的下一个节点
  • 如果当前节点值等于 val，返回下一个节点（删除当前节点）
  • 否则返回当前节点（保留当前节点）

Discussions