给你一个链表的头节点head和一个整数val , 请你删除链表中所有满足Node.val == val的节点, 并返回新的头节点.
示例 1:
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2:
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
提示:
- 列表中的节点数目在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
思路
这道题使用递归和迭代都可以完成, 两种方法的时间复杂度都为O(n), 空间复杂度为O(1). 这里使用较为简单的迭代法(递归好难)
迭代法的大致意思是设置一个虚拟节点(dummy), 指向当前结点(current)的下一个节点, 若虚拟节点的值为目标值, 则current.next = dummy.next;
此时有一个问题, 那就是若目标值为头节点, 该怎么移除? 移除头节点的操作和移除其他节点是不一样的, 因为其他节点可以靠上一个节点来移除, 而头节点没有上一个节点.
所以这里有两种方式: 创建一个虚拟头节点或为移除头节点单独写一段逻辑
代码实现
使用虚拟头节点:
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) {
return head;
}
ListNode dummy = new ListNode(-1, head); // 创建虚拟头节点
ListNode left = dummy;
ListNode right = head;
while(right != null) {
if(right.val == val) {
left.next = right.next;
} else {
left = right;
}
right = right.next;
}
return dummy.next;
}
}
不使用虚拟头节点:
class Solution {
public ListNode removeElements(ListNode head, int val) {
while(head != null && head.val == val) { // 若目标值在头节点的移除逻辑
head = head.next;
}
if(head == null) {
return head;
}
ListNode left = head;
ListNode right = head.next;
while(right != null) {
if(right.val == val) {
left.next = right.next;
} else {
left = right;
}
right = right.next;
}
return head;
}
}