删除链表节点

问题

给定单链表的头指针和一个要删除的节点的值，实现删除该节点的函数。

解答

链表节点定义

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

方法一：常规删除（给定头节点和目标值）

function deleteNode(head, val) {
  // 如果要删除的是头节点
  if (head.val === val) {
    return head.next;
  }

  let prev = head;
  let curr = head.next;

  // 遍历找到目标节点
  while (curr !== null && curr.val !== val) {
    prev = curr;
    curr = curr.next;
  }

  // 找到了，跳过该节点
  if (curr !== null) {
    prev.next = curr.next;
  }

  return head;
}

方法二：使用虚拟头节点

function deleteNode(head, val) {
  // 创建虚拟头节点，简化边界处理
  const dummy = new ListNode(-1);
  dummy.next = head;

  let prev = dummy;
  let curr = head;

  while (curr !== null) {
    if (curr.val === val) {
      prev.next = curr.next; // 删除当前节点
      break;
    }
    prev = curr;
    curr = curr.next;
  }

  return dummy.next;
}

方法三：只给定要删除的节点（经典变体）

// 不给 head，只给要删除的节点本身
function deleteNode(node) {
  // 将下一个节点的值复制过来
  node.val = node.next.val;
  // 删除下一个节点
  node.next = node.next.next;
}

测试代码

// 创建链表: 1 -> 2 -> 3 -> 4 -> 5
function createList(arr) {
  const dummy = new ListNode(-1);
  let curr = dummy;
  for (const val of arr) {
    curr.next = new ListNode(val);
    curr = curr.next;
  }
  return dummy.next;
}

// 打印链表
function printList(head) {
  const result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  console.log(result.join(' -> '));
}

// 测试
const list = createList([1, 2, 3, 4, 5]);
printList(list); // 1 -> 2 -> 3 -> 4 -> 5

const newHead = deleteNode(list, 3);
printList(newHead); // 1 -> 2 -> 4 -> 5

关键点

• 删除头节点需要特殊处理，或使用虚拟头节点统一逻辑
• 删除操作的本质是修改前驱节点的 next 指针
• 只给定待删除节点时，用”值替换”技巧：复制后继节点的值，然后删除后继节点
• 时间复杂度 O(n)，空间复杂度 O(1)
• 注意处理节点不存在的边界情况