【C++链表】
使用c++重新写一遍LeetCode707设计链表
目的是熟悉c++中链表的操作
知识点
C++链表节点的实现
在c++中，一般通过结构体来定义链表的节点，也需要写构造函数（使用初始化列表）
如：
struct ListNode{ int val; ListNode* next; //要写构造函数 //结构体中的构造函数要用初始化列表来初始化属性 ListNode(int val) :val(val), next(nullptr){} }; 访问节点中的属性遵循结构体指针操作
即利用操作符 -> 可以通过结构体指针访问结构体属性
例如，遍历链表
while(cur->next != nullptr){ cur = cur->next; } 实现一个链表节点
c++中对于链表的操作均通过指针完成，例如：
//创建一个待插入的节点 ListNode* node4add = new ListNode(val); 上述代码在堆区开辟一块新内存存放一个ListNode对象，将指针node4add指向该区域
内存释放
在c++中操作节点，如果不再需要某个节点，一定要把该节点删除（释放内存）
例如删除节点的操作中，我们将待删除节点的上一个节点指向待删除节点的后一个节点，绕过了待删除节点，实现对该节点的删除
如果是其他语言，就直接操作就行了，在c++中不行
我们还需要将待删除节点保存下来，再删除释放
void deleteAtIndex(int index) { if(index < 0 || index >= m_size){ return; } //将当前指针指向dummy ListNode* cur = m_dummy; while(index){ cur = cur->next; index--; } //要先把待删除的节点用临时节点保存，以便之后进行delete操作 //如果不删除的话会报错 ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; m_size--; } 完整代码
class MyLinkedList { public: //要先定义一个结构体作为节点 struct ListNode{ int val; ListNode* next; //要写构造函数 //结构体中的构造函数要用初始化列表来初始化属性 ListNode(int val) :val(val), next(nullptr){} }; MyLinkedList() { //初始化（定义/实现）链表的头节点和size //实际上这两个属于MyLinkedList类的成员属性，由于我们不想其被修改 //因此可以把它们写在private区 m_size = 0; m_dummy = new ListNode(0);//在堆区开辟一块新内存存放一个ListNode对象，将指针m_dummy指向该区域 } int get(int index) { if (index > (m_size - 1) || index < 0) { return -1; } //将当前指针指向头节点（即dummy的下一个） // ListNode* cur = m_dummy->next; ListNode* cur = m_dummy; while(index){ cur = cur->next; index--; } return cur->next->val;//记得返回的是cur的下一个节点，因为最初cur指向的是dummy //要么一开始就让cur指向dummy->next } void addAtHead(int val) { //创建一个待插入的节点 ListNode* node4add = new ListNode(val); node4add->next = m_dummy->next; m_dummy->next = node4add; m_size++; } void addAtTail(int val) { //创建一个待插入的节点 ListNode* node4add = new ListNode(val); ListNode* cur = m_dummy; //遍历到链表末尾处 while(cur->next != nullptr){ cur = cur->next; } //插入新节点 cur->next = node4add; m_size++; } // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。 // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点 // 如果index大于链表的长度，则返回空 // 如果index小于0，则在头部插入节点 void addAtIndex(int index, int val) { if(index > m_size){ return; }else if(index < 0){ index = 0; } //将当前指针指向dummy ListNode* cur = m_dummy; //遍历到index位置 while(index){ cur = cur->next; index--; } //找到插入位置之后开始插入 //创建一个待插入的节点 ListNode* node4add = new ListNode(val); node4add->next = cur->next; cur->next = node4add; //链表长度增加 m_size++; } void deleteAtIndex(int index) { if(index < 0 || index >= m_size){ return; } //将当前指针指向dummy ListNode* cur = m_dummy; while(index){ cur = cur->next; index--; } //要先把待删除的节点用临时节点保存，以便之后进行delete操作 //如果不删除的话会报错 ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; m_size--; } private: int m_size;//声明链表长度 ListNode* m_dummy;//声明dummy头节点 }; /** * 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); */ 707二刷错误点
1、忘记处理链表size
记得定义链表长度size
2、next的含义
举个例子
void addAtIndex(int index, int val) { if(index > m_size){ return; }else if(index < 0){ index = 0; } //将当前指针指向dummy ListNode* cur = m_dummy; //遍历到index位置 while(index){ cur = cur->next; index--; } //找到插入位置之后开始插入 //创建一个待插入的节点 ListNode* node4add = new ListNode(val); node4add->next = cur->next; cur->next = node4add; //链表长度增加 m_size++; } 这里node4add->next = cur->next;的意思是：
node4add节点的下一个节点指向cur的下一个节点A，此时cur->next代表的是一个节点
而cur->next = node4add;的意思是：
cur的下一个节点指向node4add节点，此时cur->next表示访问cur节点的next属性并对其进行操作
3、get函数，要注意cur的指向
代码注释有说明，在用dummy节点的时候不要搞错返回对象
