网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 203. 移除链表元素 ，难度为 简单。
Tag : 「链表」
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
网络异常，图片无法展示
|
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5] 复制代码
示例 2：
输入：head = [], val = 1 输出：[] 复制代码
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[] 复制代码
提示：
- 列表中的节点在范围 [0, 10^4104] 内
- 1 <= Node.val <= 50
- 0 <= k <= 50
递归
一个直观的做法是：写一个递归函数来将某个值为 val 的节点从链表中移除。
由于是单链表，无法通过某个节点直接找到「前一个节点」，因此为了方便，我们可以为递归函数多设置一个入参，代表「前一个节点」。
代码：
class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(-1); dummy.next = head; dfs(dummy, dummy.next, val); return dummy.next; } void dfs(ListNode prev, ListNode root, int val) { if (root == null) return ; if (root.val == val) { prev.next = root.next; } else { prev = root; } dfs(prev, prev.next, val); } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：忽略递归带来的额外空间开销。复杂度为 O(1)O(1)
迭代
同理，我们可以使用「迭代」方式来实现，而迭代有 while 和 for 两种写法。
代码：
class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(-1); dummy.next = head; for (ListNode tmp = dummy.next, prev = dummy; tmp != null; tmp = tmp.next) { if (tmp.val == val) { prev.next = tmp.next; } else { prev = tmp; } } return dummy.next; } } 复制代码
class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode tmp = dummy.next, prev = dummy; while (tmp != null) { if (tmp.val == val) { prev.next = tmp.next; } else { prev = tmp; } tmp = tmp.next; } return dummy.next; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.203 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
