第一版
容易出现操作空指针，要为对应的特殊情况做处理
直接在原本的链表上做处理。
分为两种情况
- 删除链表头
- 删除非表头
核心代码
class Solution { public: ListNode* removeElements(ListNode* head, int val) { if (head == NULL)return NULL; ListNode* temp, * tempnext, * Head = head, * dele_val; while (Head->val == val) { dele_val = Head; if (Head->next != nullptr)Head = Head->next; else return NULL; delete dele_val; } temp = Head; tempnext = temp->next; if (tempnext == nullptr)return Head; while (tempnext->next != nullptr) { if (tempnext->val == val) { temp->next = tempnext->next; dele_val = tempnext; delete dele_val; tempnext = temp->next; } else { temp = temp->next; tempnext = temp->next; } } if (tempnext->val == val) { temp->next = nullptr; delete tempnext; } return Head; } };
全部代码
#include <iostream> #include <vector> #include<algorithm> using namespace std; 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 LinkList { public: ListNode* head; LinkList(); //构造 ~LinkList(); //析构 void print(); //打印链表元素 inline int getLength() { return length; }; void pushBack(int data); //尾插 private: int length; }; LinkList::LinkList() { head = new ListNode(); head->next = nullptr; head->val = NULL; length = 0; } LinkList::~LinkList() { if (length == 0) { delete head; //删除头节点空间 head = nullptr; return; } ListNode* p = head->next; delete head; while (p != nullptr) { ListNode* tmpptr = p->next; delete p; p = tmpptr; } length = 0; } void LinkList::pushBack(int data) //尾插 { ListNode* temp = head; ListNode* cur = new ListNode(); cur->val = data; cur->next = nullptr; while (temp->next != nullptr) { temp = temp->next; } temp->next = cur; length++; return; } void LinkList::print() { if (length == 0) return; ListNode* temp = head->next; cout << "current list:" << endl; int i; while (temp->next!= nullptr) { cout << temp->val << ' '; temp = temp->next; } cout << temp->val << ' '; cout << endl; temp = nullptr; } class Solution { public: ListNode* removeElements(ListNode* head, int val) { if (head == NULL)return NULL; ListNode* temp, * tempnext, * Head = head, * dele_val; while (Head->val == val) { dele_val = Head; if (Head->next != nullptr)Head = Head->next; else return NULL; delete dele_val; } temp = Head; tempnext = temp->next; if (tempnext == nullptr)return Head; while (tempnext->next != nullptr) { if (tempnext->val == val) { temp->next = tempnext->next; dele_val = tempnext; delete dele_val; tempnext = temp->next; } else { temp = temp->next; tempnext = temp->next; } } if (tempnext->val == val) { temp->next = nullptr; delete tempnext; } return Head; } }; int main() { vector<int> head = { 1 }; int val = 2; LinkList TestList , TestList2; Solution a; for (int i = 0; i < head.size(); i++) { TestList.pushBack(head[i]); } TestList.print(); ListNode* temp = a.removeElements(TestList.head->next, val); TestList.head->next = temp; cout << "last list:" << endl; while (temp->next != nullptr) { cout << temp->val << ' '; temp = temp->next; } cout << temp->val << ' '; cout << endl; return 0; }
虚拟头节点法
主动在链表之前加一个虚拟头，这样将删除头节点和删除其他节点合并成一种类型
核心代码
class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* DummyHead = new ListNode(0 , head); ListNode* cur = DummyHead; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* temp = cur->next; cur->next = cur->next->next; delete temp; } else { cur = cur->next; } } head = DummyHead->next; delete DummyHead; return head; } };
全部代码
#include <iostream> #include <vector> #include<algorithm> using namespace std; 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 LinkList { public: ListNode* head; LinkList(); //构造 ~LinkList(); //析构 void print(); //打印链表元素 inline int getLength() { return length; }; void pushBack(int data); //尾插 private: int length; }; LinkList::LinkList() { head = new ListNode(); head->next = nullptr; head->val = NULL; length = 0; } LinkList::~LinkList() { if (length == 0) { delete head; //删除头节点空间 head = nullptr; return; } ListNode* p = head->next; delete head; while (p != nullptr) { ListNode* tmpptr = p->next; delete p; p = tmpptr; } length = 0; } void LinkList::pushBack(int data) //尾插 { ListNode* temp = head; ListNode* cur = new ListNode(); cur->val = data; cur->next = nullptr; while (temp->next != nullptr) { temp = temp->next; } temp->next = cur; length++; return; } void LinkList::print() { if (length == 0) return; ListNode* temp = head->next; cout << "current list:" << endl; int i; while (temp->next!= nullptr) { cout << temp->val << ' '; temp = temp->next; } cout << temp->val << ' '; cout << endl; temp = nullptr; } class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* DummyHead = new ListNode(0 , head); ListNode* cur = DummyHead; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* temp = cur->next; cur->next = cur->next->next; delete temp; } else { cur = cur->next; } } head = DummyHead->next; delete DummyHead; return head; } }; int main() { vector<int> head = { 1 }; int val = 2; LinkList TestList , TestList2; Solution a; for (int i = 0; i < head.size(); i++) { TestList.pushBack(head[i]); } TestList.print(); ListNode* temp = a.removeElements(TestList.head->next, val); TestList.head->next = temp; cout << "last list:" << endl; while (temp->next != nullptr) { cout << temp->val << ' '; temp = temp->next; } cout << temp->val << ' '; cout << endl; return 0; }
二刷
虚拟头节点
/** * 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 *duny_head = new ListNode(0,head); ListNode *cur = duny_head; while(cur->next != nullptr) { if(cur->next->val == val) { ListNode *tmp = cur->next; cur->next = cur->next->next; delete tmp; }else cur = cur->next; } ListNode *result = duny_head->next; delete duny_head; return result; } };
