LC 203. 移除链表元素
题目描述
这是 LeetCode 上的 203. 移除链表元素 ,难度为 简单。
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例 1:1
2输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
示例 2:1
2输入:head = [], val = 1
输出:[]
示例 3:1
2输入:head = [7,7,7,7], val = 7
输出:[]
提示:
- 列表中的节点在范围 [0, $10^4$] 内
- 1 <= Node.val <= 50
- 0 <= k <= 50
递归
一个直观的做法是:写一个递归函数来将某个值为 val
的节点从链表中移除。
由于是单链表,无法通过某个节点直接找到「前一个节点」,因此为了方便,我们可以为递归函数多设置一个入参,代表「前一个节点」。
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class 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(1)$
迭代
同理,我们可以使用「迭代」方式来实现,而迭代有 while
和 for
两种写法。
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14class 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;
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class 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(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.203
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!