Version: Next
203.移除链表元素
给你一个链表的头节点 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, 104] 内 1 <= Node.val <= 50 0 <= k <= 50
法1：构建新链表
- 定义一个新的头节点
newHead，表示新链表的头结点- 定义一个 节点
last指向新链表的最后一个节点- 用
head遍历链表
- 第一个不等于要删除值的节点，就是新的头节点
- 每向新链表中添加一个新节点，就让
last指向这个新节点
public static ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
ListNode newHead = null;
ListNode lastNode = null;
while (head != null) {
if (head.val != val) { // 不是要删除的值，就添加到新链表
if (lastNode == null) { // 如果为空，说明新链表还没有节点，而现在有一个head符合要求
newHead = head;// 那么它就是新头结点
lastNode = head; //此时新链表里只有一个节点，那么它也是最后一个节点
} else {
lastNode.next = head;
lastNode = head;
}
}
head = head.next;
}
// 尾节点要指向 Null
if (lastNode == null) // 如果一上来整个链表里就全是要删除的那个值
return null;
else
lastNode.next = null;
return newHead;
}
法2：虚拟头节点
对 法1 进行改进
- 一上来 newHead 就指向一个自建的节点，假设值为
0- 所以一上来 newHead 就是 lastNode
public static ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
ListNode newHead = new ListNode(0, null);
ListNode lastNode = newHead;
while (head != null) {
if (head.val != val) { // 不是要删除的值，就添加到新链表
lastNode.next = head;
lastNode = head;
}
head = head.next;
}
// 尾节点要指向 Null
lastNode.next = null;
return newHead.next; // 返回虚拟头结点的下一个节点
}