题目
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
代码
- 使用的是while而不是if,因为移除结点是一个持续的过程,直到遍历所有结点才会结束
- cur -> next -> val作为判断的结点的原因:删除一个结点时要找上一个结点和下一个结点,如果cur指向了val结点,单向链表中找不到上一个结点了,所以要通过cur -> next来找等于val的结点
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//头结点对应目标值,删除头结点
//头结点不能等于NULL,否则操作空指针就会报错
while( head != NULL && head -> val == val){ //头结点的数值域等于val
ListNode * temp = head; //创建一个temp,后续释放原head内存
head = head -> next; //将下一个节点作为头结点
delete temp; //释放原结点
}
//非头结点
ListNode* cur = head; // 定义一个临时指针指向头结点
//指向头结点的原因:删除一个结点时要找上一个结点和下一个结点,如果cur指向了val结点,单向链表中找不到上一个结点了,所以要通过cur -> next来找等于val的结点
//链表中最后一个结点怎么检查,cur -> next = NULL时,怎么进入进入循环执行if语句检查 每次检查的都是cur的下一个结点,当cur++时,此结点已经经过了检查,是可以保留的结点
while(cur != NULL && cur -> next != NULL){ //头结点本身和指向的结点不为空
if(cur -> next -> val == val){ //头结点指向的结点值等于val,有满足条件的结点存在
ListNode* temp =cur -> next; //将后续要释放的内存赋值给中间变量
cur -> next = cur -> next -> next; //从链表中删除满足条件的结点
delete temp; //释放满足条件的结点
}
else
cur = cur -> next; //累加,遍历整个链表
}
return head; //返回删除后的链表
}
};
虚拟头结点的方法
- return 的是hummyHead -> next,原来的head可能已经被删除了
//虚拟一个头结点,使得原来的头结点的操作和其余结点相同
ListNode* dummyHead = new ListNode(0);
dummyHead -> next = head; //设置的虚拟结点指向头结点
ListNode* cur = dummyHead; //创建一个用于遍历链表的临时指针
while(cur -> next != NULL) {
if(cur -> next -> val == val){
ListNode* temp = cur -> next;
cur -> next = cur -> next -> next;
delete temp;
}
else
cur = cur -> next;
}
head = dummyHead -> next; //没有这行会出错,没有这行head可能为空指针(原head可能已经被删了)
delete dummyHead; //释放创建的虚拟结点
return head;
标签:结点,cur,val,head,next,链表,移除,lc203
From: https://www.cnblogs.com/wangshoutong/p/17205658.html