链表
203. 移除链表元素
/**
* 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(0);
dummyNode->next = head;
//当前节点
ListNode* cur = dummyNode;
//遍历链表
while(cur->next != NULL){
//移除操作
if(cur->next->val == val){
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next;
}
}
//删除虚拟节点
head = dummyNode->next;
delete dummyNode;
return head;
}
};
这里以链表 1 4 2 4 来举例，移除元素4。
如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：
其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。
这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。
这样是不是就可以使用和移除链表其他节点的方式统一了呢？
来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。
最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点
707. 设计链表
这道题目设计链表的五个接口：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目文章来源：https://www.toymoban.com/news/detail-505489.html
采用的设置一个虚拟头结点（这样更方便一些，大家看代码就会感受出来）【避免了要将头结点单独抽逻辑出来操作的麻烦】文章来源地址https://www.toymoban.com/news/detail-505489.html
class MyLinkedList {
public:
struct LinkedNode{
int val;
LinkedNode* next;
LinkedNode(int val):val(val),next(nullptr){}
};
//声明一个私有成员变量
private:
LinkedNode* _dummyHead;
int _size;
public:
MyLinkedList() {
_dummyHead = new LinkedNode(0);
_size = 0;
}
int get(int index) {
//判断index合法性
if(index > (_size - 1) || index < 0){
return -1;
}
//因为索引值是从原链表算，需要将头节点放在虚拟节点后一位
LinkedNode* cur = _dummyHead->next;
//index是从0开始的，0就是头结点
while(index--){
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
//构造新节点
LinkedNode* newNode = new LinkedNode(val);
//添加操作 先将添加的节点指向插入的位置
//再将原来的头结点指向新节点完成添加
//如果先将dummyHead指向新节点，会丢失新节点指向的下一节点的位置
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
void addAtTail(int val) {
//遍历到最后一个节点
//添加操作即可
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next != nullptr){
//指向遍历操作
cur = cur->next;
}
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if(index > _size) return;
//index<0 就在头部插入节点
if(index < 0) index = 0;
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(index--){
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if(index >= _size || index < 0){
return;
}
LinkedNode* cur = _dummyHead;
while(index--){
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
//delete释放tmp指针内存
//被delete后的tmp值不一定是NULL，而是随机值
//所以需要将tmp置空
tmp = nullptr;
_size--;
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
206. 反转链表
/**
* 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* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
//利用两个指针改变指针指向
//tmp：当改变指向时有可能会丢失后面的指向，提前保存
while(cur != nullptr){
ListNode* tmp = cur->next;
cur->next = pre;
//改变指向后移动指针
pre = cur;
cur = tmp;
}
return pre;
}
};
到了这里，关于203.移除链表元素|707.设计链表|206.反转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
