删除链表的节点

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

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

注意：此题对比原题有改动

示例 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.

方法一：单指针+虚拟头节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode deleteNode(ListNode head, int val) {
    if(head == null) return null;
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode cur = dummyHead;
    while(cur.next != null) {
      if(cur.next.val == val) {
        cur.next = cur.next.next;
      } else {
        cur = cur.next;
      }
    }
    return dummyHead.next;
  }
}

var deleteNode = function(head, val) {
  if(head == null) return null;
  let dummyHead = new ListNode(0);
  dummyHead.next = head;
  let cur = dummyHead;
  while(cur.next !== null) {
    if(cur.next.val === val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return dummyHead.next;
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.8 MB, 在所有 Java 提交中击败了69.21%的用户

方法二：递归

递归过程：

对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。
如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next
如果 head 的节点值不等于 val，则 head 保留，因此删除操作后的头节点还是 head

递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode removeElements(ListNode head, int val) {
    if(head == null ) return null;
    head.next = removeElements(head.next, val);
    return head.val == val ? head.next : head;
  }
}

var deleteNode = function(head, val) {
  if(head == null) return null;
  head.next = deleteNode(head.next, val);
  return head.val === val ? head.next : head;
};

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。递归过程中需要遍历链表一次。
空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用栈，最多不会超过 n 层。

执行结果：通过

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.8 MB, 在所有 Java 提交中击败了55.35%的用户