移除链表元素
题目
题意:删除链表中等于给定值 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
输出:[]
初见思路
就操作链表咯
常规思路
如果直接使用头节点作为当前节点的话,在删除头节点时的操作会与删除其他节点时不一致
要统一所有节点的删除方式,需要引入虚拟节点dummy
这样,每当需要删除某个节点时(包括头节点)
都可以遵循:将待删除节点的前一个节点的next指针指向待删除节点的后一个节点 这样一个规则
解题模板
不使用虚拟节点
具体还有两种写法:使用pre、cur指针和只用cur指针
具体看代码:
class Solution {
public ListNode removeElements(ListNode head, int val) {
//删除头节点的情况
while(head != null && head.val == val){
head = head.next;
}
//不要忘了,如果头节点为空就直接退出
if(head == null){
return head;
}
//删除其他节点的情况
//正常情况
ListNode pre = head;
ListNode cur = head.next;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
// //只使用一个临时节点cur
// //当前节点的指针应该指向head而不是head.next
// //因为如果要删除的就是当前cur指向的值,那么直接指向head的方式就有问题,因为在单向链表中,它找不到待删除节点的上一个节点
// //而第二种方式就避免了这种情况
// ListNode cur = head;
// while(cur != null){
// while(cur.next != null && cur.next.val == val){
// cur.next = cur.next.next;
// }
// cur = cur.next;
// }
return head;//不是返回临时节点cur,要找回最开始的头节点head
}
}
使用虚拟节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){//先判断头节点是否为空,防止操作空指针
return head;
}
//创建一个虚拟节点
ListNode dummy = new ListNode(1, head);
//定义前一个节点pre与当前节点cur
ListNode pre = dummy;
ListNode cur = head;
while(cur != null){//要用循环而不是if,因为删除操作应该是连续的
if(cur.val == val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
//注意!要返回虚拟节点的下一个节点,即头节点。而不是直接返回头节点,因为原来的head有可能已经被删了
return dummy.next;
}
}
反正以后就记住使用虚拟节点的方式就行,用的时候也优先这种方式
标签:head,ListNode,cur,val,LeetCode,链表,移除,next,节点 From: https://www.cnblogs.com/DAYceng/p/17047947.html