目录链表理论基础203.移除链表元素707.设计链表206.反转链表链表理论基础链表的类型单链表、双链表、循环链表各自的特点单链表只能向后查询、双链表可双向查询、循环链表首尾连接链表查找和增删的复杂度和数组查找和增删的复杂度对比如下还有链表的定义方式自己在学C基础时已掌握。203.移除链表元素文章视频链接 完成状态没看文章编完报了RE问DSdebug后AC之前在C基础学过链表的构造、移除和增加但出现了一些细节错误已在代码中注释。ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead; while(cur-next!nullptr){ //思路如果cur的下一个的值是val则删除把下下个节点赋值给下个节点 //否则就更新cur到下一个节点 //注意一定要在if的else语句里更新cur否则会出现在出现连续val的时候跳过val的情况 //还会出现在删除尾节点的时候空指针解引用的问题导致RE if(cur-next-valval){ cur-next cur-next-next; }else{ curcur-next; } } return dummyHead-next; }707.设计链表文章链接 完成状态花费1h完成了单链表形式AC本题每个函数的编写不是很难但是个人对类还是不够熟悉导致一些细节上写错。需要注意写类的成员变量链表长度节点虚拟头节点节点需要单独定义结构体包括值变量地址变量构造函数类内需要类的初始化函数初始化头节点和链表长度。建议对成员变量进行封装所以放在private中成员函数可放在public。还需注意题目说的是链表节点下标从0开始函数实现较为简单就是简单的找索引和增删操作。class MyLinkedList { private: int _size; struct ListNode{ int val; ListNode* next; ListNode(int x): val(x),next(nullptr){} };//放在虚拟头节点变量的前面定义 ListNode* _dummyHead; public: //初始化函数 MyLinkedList(){ _dummyHead new ListNode(0); _size 0; } //得到规定索引的值 int get(int index) { ListNode* cur _dummyHead; if(index0 || index_size) return -1; while(index--) cur cur-next; return cur-next-val; } //在头前增加规定值 void addAtHead(int val) { ListNode* newNode new ListNode(val); newNode-next _dummyHead-next; _dummyHead-next newNode; _size; } //在尾后增加规定值 void addAtTail(int val) { ListNode* tailNode new ListNode(val); ListNode* cur _dummyHead; for(int i0;i_size;i){ curcur-next; } cur-next tailNode; _size; } //在规定索引前插入规定值 void addAtIndex(int index, int val) { ListNode* cur _dummyHead; ListNode* newNode new ListNode(val); if(index _size) addAtTail(val); else if(index_size){ while(index--){ curcur-next; } newNode-next cur-next; cur-next newNode; _size; } } //删除规定索引的值 void deleteAtIndex(int index) { ListNode* cur _dummyHead; if(index _size index0){ while(index--) curcur-next; ListNode* temp cur-next; cur-next cur-next-next; delete temp; temp nullptr; _size--; } } };206.反转链表文章链接 完成状态自己没想出来看了文章思路后用时15minAC思路总结本题思路重点就是直接将指向反转需要用到双指针。初始化cur为headruc为空cur从头遍历到尾ruc在cur左边跟随cur前进。之后进入循环每一次循环执行1. 保存cur的下一个节点为temp2. 将cur指向ruc3. ruc更新为cur4. cur更新为temp。最后一次循环结束cur更新到了最后一个节点ruc更新到了倒数第二个元素但还没有执行转向操作需单独控制cur-next ruc。ListNode* reverseList(ListNode* head) { if(head nullptr) return nullptr; else{ ListNode* ruc nullptr; ListNode* cur head; while(cur-next ! nullptr){ ListNode* temp cur-next;//保存cur的下一个节点 cur-next ruc;//将cur转向指向ruc ruc cur;//将ruc右移更新到cur位置 cur temp;//cur右移更新到temp位置 } cur-next ruc; return cur; } }总结今天复习了链表的定义、增删操作重写了链表的几个基本操作函数复习了类的相关知识学到了双指针实现指向反转的反转链表操作。继续坚持
代码随想录算法训练营Day-3 | 链表理论基础、LeetCode：203.移除链表元素、707.设计链表、206.反转链表
发布时间：2026/7/15 4:48:17
目录链表理论基础203.移除链表元素707.设计链表206.反转链表链表理论基础链表的类型单链表、双链表、循环链表各自的特点单链表只能向后查询、双链表可双向查询、循环链表首尾连接链表查找和增删的复杂度和数组查找和增删的复杂度对比如下还有链表的定义方式自己在学C基础时已掌握。203.移除链表元素文章视频链接 完成状态没看文章编完报了RE问DSdebug后AC之前在C基础学过链表的构造、移除和增加但出现了一些细节错误已在代码中注释。ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead; while(cur-next!nullptr){ //思路如果cur的下一个的值是val则删除把下下个节点赋值给下个节点 //否则就更新cur到下一个节点 //注意一定要在if的else语句里更新cur否则会出现在出现连续val的时候跳过val的情况 //还会出现在删除尾节点的时候空指针解引用的问题导致RE if(cur-next-valval){ cur-next cur-next-next; }else{ curcur-next; } } return dummyHead-next; }707.设计链表文章链接 完成状态花费1h完成了单链表形式AC本题每个函数的编写不是很难但是个人对类还是不够熟悉导致一些细节上写错。需要注意写类的成员变量链表长度节点虚拟头节点节点需要单独定义结构体包括值变量地址变量构造函数类内需要类的初始化函数初始化头节点和链表长度。建议对成员变量进行封装所以放在private中成员函数可放在public。还需注意题目说的是链表节点下标从0开始函数实现较为简单就是简单的找索引和增删操作。class MyLinkedList { private: int _size; struct ListNode{ int val; ListNode* next; ListNode(int x): val(x),next(nullptr){} };//放在虚拟头节点变量的前面定义 ListNode* _dummyHead; public: //初始化函数 MyLinkedList(){ _dummyHead new ListNode(0); _size 0; } //得到规定索引的值 int get(int index) { ListNode* cur _dummyHead; if(index0 || index_size) return -1; while(index--) cur cur-next; return cur-next-val; } //在头前增加规定值 void addAtHead(int val) { ListNode* newNode new ListNode(val); newNode-next _dummyHead-next; _dummyHead-next newNode; _size; } //在尾后增加规定值 void addAtTail(int val) { ListNode* tailNode new ListNode(val); ListNode* cur _dummyHead; for(int i0;i_size;i){ curcur-next; } cur-next tailNode; _size; } //在规定索引前插入规定值 void addAtIndex(int index, int val) { ListNode* cur _dummyHead; ListNode* newNode new ListNode(val); if(index _size) addAtTail(val); else if(index_size){ while(index--){ curcur-next; } newNode-next cur-next; cur-next newNode; _size; } } //删除规定索引的值 void deleteAtIndex(int index) { ListNode* cur _dummyHead; if(index _size index0){ while(index--) curcur-next; ListNode* temp cur-next; cur-next cur-next-next; delete temp; temp nullptr; _size--; } } };206.反转链表文章链接 完成状态自己没想出来看了文章思路后用时15minAC思路总结本题思路重点就是直接将指向反转需要用到双指针。初始化cur为headruc为空cur从头遍历到尾ruc在cur左边跟随cur前进。之后进入循环每一次循环执行1. 保存cur的下一个节点为temp2. 将cur指向ruc3. ruc更新为cur4. cur更新为temp。最后一次循环结束cur更新到了最后一个节点ruc更新到了倒数第二个元素但还没有执行转向操作需单独控制cur-next ruc。ListNode* reverseList(ListNode* head) { if(head nullptr) return nullptr; else{ ListNode* ruc nullptr; ListNode* cur head; while(cur-next ! nullptr){ ListNode* temp cur-next;//保存cur的下一个节点 cur-next ruc;//将cur转向指向ruc ruc cur;//将ruc右移更新到cur位置 cur temp;//cur右移更新到temp位置 } cur-next ruc; return cur; } }总结今天复习了链表的定义、增删操作重写了链表的几个基本操作函数复习了类的相关知识学到了双指针实现指向反转的反转链表操作。继续坚持
