力扣203移除链表元素：思路分析+代码实现+方法总结（伪头节点法&递归）

谁借莪１个温暖的怀抱￠ 2024-04-24 14:38 72阅读 0赞

#### 文章目录 ####

*  第一部分：题目描述
 *  第二部分：题解
 *   *  2.1 伪头节点遍历
     *  2.2 递归

## 第一部分：题目描述 ##

? 链接：[203. 移除链表元素 - 力扣（LeetCode）][203. _ - _LeetCode]

⭐ 难度：简单

![image-20230513004407899][]

## 第二部分：题解 ##

### 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 递归 ###

思路，递归函数负责返回：从当前节点（我）开始，完成删除的子链表

1.  若我与 val 相等，应该返回下一个节点递归结果
2.  若我与 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;
            }
        }
    }

[203. _ - _LeetCode]: https://leetcode.cn/problems/reverse-linked-list/
[image-20230513004407899]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/19f693f4cfca45c3a80bad65128f1977.png