给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
思路： 搞一个链表，以第一个值不等于传入整数val的结点为头节点，再创建一个尾结点；来串联所有值不等于val的节点；最终返回新链表的头节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null) return head;
ListNode newHead = null;//新链表的头结点
ListNode newTail = null;//新链表的尾结点
while(head != null) {
if(head.val != val) {
//等于空说明头尾结点都是空
if(newTail == null) {
newHead = head;
}else {
//将head拼接到newTail的后面
newTail.next = head;
}
newTail = head;
}
//下一个结点
head = head.next;
}
if(newTail!=null) {//尾结点要清空
newTail.next = null;
}else {//newTail==null 意味着传入的链表所有结点都是要删的
return null;
}
//返回新的头节点
return newHead;
}
}
优化思路：使用虚拟头节点
class Solution {
public ListNode removeElements(ListNode head, int val) {
//0.边界处理
if(head==null) return head;
//1.定义虚拟头结点
ListNode newHead = new ListNode(0);
ListNode newTail = newHead;
//2.遍历传入的链表 给新链表赋值
while(head != null) {
if(head.val != val) {
newTail.next = head;//将结点拼接到尾结点后面
newTail = head;//更新尾结点
}
head = head.next;
}
//3.清空尾结点
newTail.next = null;
//4.返回虚拟头节点的下一个节点
return newHead.next;
}
}
虚拟头结点步骤最少解法
/**
思路：
1.搞一个链表，以第一个值不等于传入整数val的结点为头结点，
2.定义一个尾结点用来串连所有值不等于val的结点
3.返回新链表的头结点
时间复杂度：O(n)
空间复杂度：O(1)
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//0.边界判断
if(head==null) return null;
//1.定义需要的数据结构
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode tailNode = dummyHead;
//2.循环过滤值等于val的结点
while(tailNode.next != null) {
//值相同就删除
if(tailNode.next.val == val) {
tailNode.next = tailNode.next.next;
}else {//不相同就继续
tailNode = tailNode.next;
}
}
//3.返回新链表
return dummyHead.next;
}
}
