203. Remove Linked List Elements

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

递归

• 时间复杂度 O(N)，空间复杂度O(1)
• Runtime: 84 ms, faster than 94.98%
• Memory Usage: 44.2 MB, less than 11.47%

/**
 * 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)，空间复杂度O(1)
• Runtime: 88 ms, faster than 84.73%
• Memory Usage: 43.9 MB, less than 27.51%

不相等的时候就复制，否则跳过。

/**
 * 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 dummy = new ListNode();
  let cur = dummy;
  while (head !== null) {
    if (head.val !== val) {
      cur.next = head;
      cur = cur.next;
    }
    head = head.next;
  }
  cur.next = null;
  return dummy.next;
};

更容易理解

• • 时间复杂度 O(N)，空间复杂度O(1)
• Runtime: 84 ms, faster than 94.98%
• Memory Usage: 43.9 MB, less than 27.51%

/**
 * 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 dummy = new ListNode(0);
  dummy.next = head;
  let cur = dummy;
  while (cur.next !== null) {
    if (cur.next.val === val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next
    }
  }
  return dummy.next;
};