「力扣」第 203 题：移除链表元素（简单）
- 英文网址：203. Remove Linked List Elements ；
- 中文网址：203. 删除链表中的结点 。
删除链表中等于给定值 val 的所有节点。
示例：
输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
1、设计第 $1$ 个结点，因此需要设置虚拟头结点。
2、两种方法：（1）递归；（2）穿针引线。
方法一：穿针引线
Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
// 下面，我们将 LeetCode 中的给出的链表的节点这个类进行一些扩展，方便我们的调试
// 1、给出一个数字数组，通过数组构建数字链表
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
// 体会这里 this 指代了什么，其实就是 head
// 因为这是一个构造函数，所以也无须将 head 返回
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
// 2、重写 toString() 方法，方便我们查看链表中的元素
@Override
public String toString() {
StringBuilder s = new StringBuilder();
// 还是要特别注意的是，理解这里 this 的用法
ListNode cur = this;
while (cur != null) {
s.append(cur.val).append(" -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
public class Solution {
// 穿针引线
public ListNode removeElements(ListNode head, int val) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode cur = dummyNode;
while (cur.next != null) {
if (cur.next.val == val) {
// 待删除的结点
ListNode deleteNode = cur.next;
cur.next = deleteNode.next;
deleteNode.next = null;
} else {
cur = cur.next;
}
}
return dummyNode.next;
}
public static void main(String[] args) {
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
Solution solution = new Solution();
solution.removeElements(head, 6);
System.out.println(head);
}
}方法二：使用递归的方法
Python 代码：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def removeElements(self, head, val):
if head is None:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else head思路：先给出一个容易想到的解法，但是这个解法对于删除头结点的逻辑写得比较长。
Java 代码：（代码比较冗长，没有意义，可以跳过不看，只要跟头结点有关的问题，要设置虚拟头结点就好了。）
/**
* 基本思路：只要当前遍历的节点的下一个节点不为空
* 把它拿出来比较一下目标值：
* 如果和目标值相同，就（1）先把要删除的节点存一下。
* （2）当前的节点的下一个引用指向要删除节点的下一个引用。
* （3）把要删除节点的下一个节点的引用置为 null。
* 但是，特别要注意：这种方法对于，如果要删除的节点是头结点的方式，并不适用
*
* @param head
* @param value
* @return
*/
public ListNode removeElements(ListNode head, int value) {
// 这里陷阱很多，要特别注意测试用例为"要删除的节点值连续出现在链表表头的情况"
// 例如，待考察链表 {1, 1, 1, 2, 3, 4, 5} ，待删除的元素的值是 1 的情况
// 为了删除头结点，我们编写了很长的一段代码
while (head != null && head.val == value) {
ListNode delNode = head;
head = delNode.next;
delNode = null;
}
if (head == null) {
return null;
}
ListNode current = head;
while (current.next != null) {
if (current.next.val == value) {
ListNode delNode = current.next;
current.next = delNode.next;
delNode.next = null;
} else {
current = current.next;
}
}
return head;
}下面介绍一种设立链表的虚拟头结点的技巧，使得删除头结点的逻辑可以合并到删除非链表头结点的逻辑中。
思路很简单，就是在带考察的链表前面加上一个虚拟节点，使得原来的头结点不是头结点。
Java 代码：
public ListNode removeElements(ListNode head, int value) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode current = dummyHead;
while (current.next != null) {
if (current.next.val == value) {
ListNode delNode = current.next;
current.next = delNode.next;
delNode = null;
} else {
current = current.next;
}
}
ListNode retNode = dummyHead.next;
dummyHead = null;
return retNode;
}思路：
1、使用虚拟头结点；
2、掌握递归写法。
重点：千万不要忘记，还有递归写法。
Python 代码：使用递归，假设小一个规模的问题已经求解，然后处理原问题。
class Solution:
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if head is None:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else headJava 代码：
public ListNode removeElements(ListNode head, int val) {
// 首先处理递归到底的情况，直接返回 null
if (head == null) {
return head;
}
// 假设下一个结点开始的链表已经处理完了
ListNode res = removeElements(head.next, val);
// 再将头结点和除了头结点以外的链表部分合并考虑
if (head.val == val) {
return res;
} else {
head.next = res;
return head;
}
}
