wordpress搜索全站,关键词资源,做网站万网,整合营销传播之父提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 链表理论基础203.移除链表元素思路与重点 707.设计链表思路与重点 206.反转链表思路与重点 链表理论基础
C/C的定义链表节点方式#xff1a;
// 单链表
struct L… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 链表理论基础203.移除链表元素思路与重点 707.设计链表思路与重点 206.反转链表思路与重点 链表理论基础
C/C的定义链表节点方式
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
数组与链表的对比 203.移除链表元素
题目链接203. 移除链表元素 - 力扣LeetCode讲解链接代码随想录 (programmercarl.com)状态提交一次后AC。
思路与重点
使用了一个虚拟头节点指向题目给出的头节点然后遍历链表开始删除最后返回虚拟头节点的next指针即可。主要使用C时不要忘记释放掉被删除节点占用的空间
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy_head new ListNode(-1, head);ListNode* cur dummy_head;while(cur-next ! nullptr){if(cur-next-val val){ListNode* temp cur-next-next;delete cur-next;cur-next temp;}else cur cur-next;}head dummy_head-next;delete dummy_head;return head;}
};链表的定义具有递归的性质因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点可以用递归实现。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 基础情况空链表if (head nullptr) {return nullptr;}// 递归处理if (head-val val) {ListNode* newHead removeElements(head-next, val);delete head;return newHead;} else {head-next removeElements(head-next, val);return head;}}
};707.设计链表
题目链接707. 设计链表 - 力扣LeetCode讲解链接代码随想录 (programmercarl.com)状态直接看题解了。
思路与重点
使用虚拟头结点可以很大降低写代码的复杂程度。注意LinkedNode* cur _dummyHead;和LinkedNode* cur _dummyHead-next;
class MyLinkedList {
public:struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};MyLinkedList() {_dummyHead new LinkedNode(0);_size 0;}int get(int index) {if(index 0 || index _size){return -1;}LinkedNode* cur _dummyHead-next;while(index--){cur cur-next;}return cur-val;}void addAtHead(int val) {LinkedNode* newNode new LinkedNode(val);newNode-next _dummyHead-next;_dummyHead-next newNode;_size;}void addAtTail(int val) {LinkedNode* newNode new LinkedNode(val);LinkedNode* cur _dummyHead;while(cur-next) cur cur-next;cur-next newNode;_size; }void addAtIndex(int index, int val) {if(index _size) return;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 0 index _size){LinkedNode* cur _dummyHead;while(index--){cur cur-next;}LinkedNode* temp cur-next;cur-next cur-next-next;delete temp;temp nullptr;_size--;} else return;}private:LinkedNode* _dummyHead;int _size;
};206.反转链表
题目链接206. 反转链表 - 力扣LeetCode讲解链接代码随想录 (programmercarl.com)状态直接去看卡哥视频了。
思路与重点
用双指针法很好解决不需要用新的链表分配空间。卡哥的视频讲的是真清晰啊用以下的动图很好理解。 class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur head;ListNode* pre nullptr;ListNode* temp nullptr;while(cur){temp cur-next;cur-next pre;pre cur;cur temp;}return pre;}
};也可以用递归的方式解决递归的解决思路其实和双指针法一样。
class Solution {
public:ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}ListNode* reverse(ListNode* pre, ListNode* cur){if(!cur) return pre;ListNode* temp cur-next;cur-next pre;return reverse(cur, temp);}
};
