203 移除链表元素
移除链表元素本质上步骤为:
- 找到待移除元素curNode的前驱节点prevNode和后继节点nextNode(curNode->next)
- prevNode->next = curNode->next
- 释放内存delete curNode
有两种做法:原链表操作和引入哑节点
-
原链表操作意味着需要分两步操作
-
因为头部节点没有前驱节点,因此需要额外处理。处理方法很简单:
-
其他节点正常处理
-
-
引入哑节点
- 引入哑节点有个好处是,所有节点(包括头节点)能够采用统一的操作,因为它让头节点也拥有了前驱节点
原链表操作
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(!head)
return head;
while(head && head->val == val){
ListNode* tmp = head;
head = head->next;
delete tmp;
}
//到这一步,head有两种可能,nullptr 或者 head->val != val
ListNode* cur = head;
// cur可能为nullptr,因此需要判断cur是否为nullptr再取cur->next
// cur->next可能为空,所以需要判断cur->next是否为nullptr再取cur->next->val
while(cur && cur->next){
if(cur->next->val == val){
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else
cur = cur->next;
}
return head;
}
};
引入哑节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 为了保证操作的统一性,引入哑节点
ListNode* dummyNode = new ListNode(-1,head);
ListNode* cur = dummyNode;
// 边界条件:判断要删除的节点是否为空
while(cur->next != nullptr){
if(cur->next->val == val){
ListNode* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
}
// 这里要注意:一定要用else
// 因为删了节点之后,cur->next改变了,需要先判断cur->next是否为空再取cur->next->val
else
cur = cur->next;
}
head = dummyNode->next;
delete dummyNode;
return head;
}
};