203. 移除链表元素
题目链接:203.移除链表元素
题目内容:
理解题意:就是单纯的删除链表中所有值等于给定的val的节点。上一篇博客中介绍了链表的基础操作,在删除链表中节点时,需要注意的是头节点:
- 如果没有虚拟头节点,那么对头节点的删除需要做不同的处理,head = head->next;
- 如果有虚拟头节点,那么所有的节点操作都是一致的,将待删除节点的前驱节点和后驱节点连接起来,并释放待删除节点对应的地址空间。
另外,由于链表的定义就是递归的,因此可以考虑使用递归,从最后一个节点开始,判断是否满足待删除条件。
解法①:头节点单独判断
在没有虚拟头节点的情况下,头节点需要单独判断。如果头节点的值就等于val,那么新的头节点head = head->next。然后呢?此时的新head对应节点的值是否等于val呢,如果等于val,那么新的头节点也要删除,删除以后head再次赋值head = head->next。 那么新的head又和给定val相等吗? ——不难发现,判断头节点是否等于val这里应该是循环的,循环直到head->val != va或者head == nullptr才行。
代码如下(C++):
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//单独判断头节点 【用循环】
while(head && head->val == val){
head = head->next;
}
ListNode *preNode = NULL, *currNode = head; //preNode是前驱节点,currNode是当前节点
while(currNode){
//删除节点
if(currNode->val == val){
preNode->next = currNode->next;
delete currNode;
currNode = preNode->next;
}
//直接后移
else{
preNode = currNode;
currNode = currNode->next;
}
}
return head;
}
};
如果不一开始就判断头节点,而是在查找值等于val的节点,并删除的过程中,对头节点单独处理的话,怎么知道当前节点是头节点呢? ——删除节点的时候,需要有当前节点currNode的指针,也需要其前驱节点preNode的指针【删除节点的时候,需要将其前驱节点的next指向后驱节点。单向链表通过当前节点可以找到后驱节点,但是不用一个变量存前驱节点的话,是不能通过当前节点直接定位到前驱节点的。】如果当前节点是头节点的话,preNode是NULL,代码如下(C++):
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* currNode = head;
ListNode* preNode = NULL;
while(currNode != nullptr){
//当前节点和目标val相等,删除
if(currNode->val == val){
//删除的是头节点
if(preNode == NULL){
head = currNode->next; //新head
delete currNode;
currNode = head;
}
//删除其他节点
else{
preNode->next = currNode->next;
delete currNode;
currNode = preNode->next;
}
}
//当前节点和目标val不相等,preNode和currNode直接向后移动
else{
preNode = currNode;
currNode = currNode->next;
}
}
return head;
}
};
解法②:虚拟头节点
添加一个虚拟头节点,那么原链表中所有节点操作都一样,不需要对头节点单独判断,代码如下(C++):
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummyhead = new ListNode(0);//构造一个虚拟头节点
dummyhead->next = head; //将head赋值给其next,建立dummyhead和head之间的连接
ListNode *currNode = head, *preNode = dummyhead; //当前节点、前驱节点
while(currNode){
//删除节点
if(currNode->val == val){
preNode->next = currNode->next;
delete currNode;
currNode = preNode->next;
}
else{
preNode = currNode;
currNode =currNode->next;
}
}
head = dummyhead->next;
delete dummyhead;
return head;
}
};
解法③:递归
链表的定义就是递归的,因此可以考虑用递归的方法求解。
思路:①寻找递归终止条件,是head=null;②对于当前节点head,递归调用删除节点的函数,去删除当前节点之后的链表里面满足题意的节点【即removeElements(head->next, val)】,并返回剩下链表删除节点后的头节点;并将removeElements()返回的结果赋值给head->next;③对于当前节点,判断是否满足题意,如果等于val就删除,那么包括当前节点head在内的这一段链表的头节点就是head->next,返回head->next;如果不删除,就直接返回head。
代码如下(C++):文章来源:https://www.toymoban.com/news/detail-664743.html
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//递归终止条件是head=null,即一直递归调用到最后一个节点的next
if(head == nullptr)
return head;
//当前节点的next指向后半截链表删除节点后返回的头节点
head->next = removeElements( head->next ,val);
//判断当前节点是否需要删除
if(head->val == val)
return head->next;
else
return head;
}
};
递归求解,不仅要遍历链表各个节点并判断,并且涉及到函数的递归调用,时间和空间开销都比之前解法要大。文章来源地址https://www.toymoban.com/news/detail-664743.html
到了这里,关于【leetcode 力扣刷题】移除链表元素 多种解法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!