JS算法-删除链表节点

本文来自于leetcode 第 237 题 和 剑指 offer 第 18 题。

题目描述

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点。

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
复制代码

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
复制代码

提示：

- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
复制代码

代码展示

/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
  node.val = node.next.val;
  node.next = node.next.next;
};
复制代码

题目描述

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

返回删除后的链表的头节点。

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
复制代码

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
复制代码

代码展示

方法一：单指针

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
  let p = head;
  if (head.val === val) return head.next;
  while(p) {
    if (p.next && p.next.val === val && !p.next.next) {
      p.next = null;
      break;
    }
    if (p.val === val) {
      p.val = p.next.val;
      p.next = p.next.next;
    }
    p = p.next;
  }
  return head;
};
复制代码

方法二：双指针

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
  if (head.val === val) return head.next;
  let cur = head;
  let prev = head.next;
  while(prev) {
    if (prev && prev.val === val) {
      cur.next = prev.next;
    }
    cur = cur.next;
    prev = prev.next;
  }
  return head;
};
复制代码

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(1)。

总结

双指针相比单指针性能更好，代码更为简洁明了。