第一部分：题目描述
🏠 链接：203. 移除链表元素 - 力扣（LeetCode）
⭐ 难度：简单
第二部分：题解
2.1 伪头节点遍历
class Solution { public ListNode removeElements(ListNode head, int val) { // 1.先定义一个伪头节点，它的 next 就是链表的第一个元素 head ListNode pseudoHead = new ListNode(-1, head); // 2.定义 tmp 指针用于 链表的遍历 ListNode tmp = pseudoHead; // 3.满足 tmp 的下一个节点不为空时，进行 while // 如果为空则说明已经遍历到了链表末尾，遍历完成 while (tmp.next != null) { // 4.判断 tmp 下一个节点是否等于目标值 val if (tmp.next.val == val) { // 如果相等就将 tmp 的下一个节点更改为 下下个节点 tmp.next = tmp.next.next; } else { // 如果不相等则 tmp 继续向后移动 tmp = tmp.next; } } // 5.返回链表的头节点 return pseudoHead.next; } }
❓ 为什么是用tmp.next来遍历全部节点
其实，这个问题是由单链表的特性所导致的，每一个节点只有该节点的上一个节点知道该节点的位置，如果用自身来遍历的话，当满足 tmp.val = val 时，应该删除自身，这时候如何将该 tmp 的上一个节点与 tmp 的下一个节点所联系是一个问题。
2.2 递归
思路，递归函数负责返回：从当前节点（我）开始，完成删除的子链表
- 若我与 val 相等，应该返回下一个节点递归结果
- 若我与 val 不等，应该返回我，但我的 next 应该更新（让我能带上后续删过的子链表）
// 链表：1 -> 2 -> 6 -> 3 -> 6 // 目标值val：6 removeElements(ListNode head=1, int val=6){ 1.next=removeElements(ListNode head=2, int val=6){ 2.next=removeElements(ListNode head=6, int val=6){ removeElements(ListNode head=3, int val=6){ 3.next=removeElements(ListNode head=6, int val=6){ removeElements(ListNode head=null, int val=6){ // 没有节点,返回 return null } } return 3 -> null } } return 2 -> 3 -> null } return 1 -> 2 -> 3 -> null }
代码：
class Solution { public ListNode removeElements(ListNode head, int val) { // 如果当前节点为 null 则直接返回 null 即可，这是递归的退出条件 if (head == null) { return null; } // return 返回的结果是作为上一层节点的下一个节点（也可能没有上一层了，就是作为了头节点） if (head.val == val) { // 如果节点值 等于 目标值 // 则应该删除该节点，那么直接继续递归无需关心该节点 return removeElements(head.next, val); } else { // 如果 节点值 不等于 目标值 // 就应该保留该节点，继续递归以确认 当前节点 的 下一个节点 head.next = removeElements(head.next, val); // 递归回来，返回当前节点即可 return head; } } }
