[LeetCode] 203. Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

The number of nodes in the list is in the range [0, 104].
1 <= Node.val <= 50
0 <= k <= 50

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

在实现 JS 版本之前我有实现过 Java 版本，很奇怪为什么 discussion 里面大多数 JS 版本的解法都没有用 dummy node。这个题用 dummy node 的用意在于包括 head 节点在内，都有可能是需要被删除的点，所以如果 dummy.next 节点需要被删除，则我们可以在走过去之前就把这个节点删除了。leetcode 上也有另外几道链表的题有涉及到同样的思路，大多都是需要删除某些特定的节点。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public ListNode removeElements(ListNode head, int val) {
 3         // corner case
 4         if (head == null) {
 5             return head;
 6         }
 7         // normal case
 8         ListNode dummy = new ListNode(0);
 9         dummy.next = head;
10         ListNode cur = dummy;
11         while (cur.next != null) {
12             if (cur.next.val == val) {
13                 cur.next = cur.next.next;
14             } else {
15                 cur = cur.next;
16             }
17         }
18         return dummy.next;
19     }
20 }

JavaScript实现

 1 /**
 2  * @param {ListNode} head
 3  * @param {number} val
 4  * @return {ListNode}
 5  */
 6 var removeElements = function(head, val) {
 7     if (head === null) return head;
 8     let dummy = new ListNode(0);
 9     dummy.next = head;
10     let cur = dummy;
11     while (cur.next != null) {
12         if (cur.next.val === val) {
13             cur.next = cur.next.next;
14         } else {
15             cur = cur.next;
16         }
17     }
18     return dummy.next;
19 };

LeetCode 题目总结