上海html5网站制作公司,3一5万电动汽车,网站域名使用期,网站使用微软雅黑2023.12.1 代码随想录刷题Day3
1. 203移除链表元素 对于链表的各种操作备考时也是烂熟于心#xff0c;这么长时间没写过相关代码#xff0c;也确实忘了很多#xff0c;关于移除链表元素#xff0c;逻辑其实很简单#xff0c;主要还是看对指针的使用是否熟悉#xff0c;其…2023.12.1 代码随想录刷题Day3
1. 203移除链表元素 对于链表的各种操作备考时也是烂熟于心这么长时间没写过相关代码也确实忘了很多关于移除链表元素逻辑其实很简单主要还是看对指针的使用是否熟悉其次就是最关键的头节点的使用我个人是比较习惯加头节点头节点可以使得对链表的操作全部统一不用特殊特殊某个节点很方便。思路很简单加入头节点后遍历一遍链表节点值如果是要删除的值直接将上节点的next连接到要删除节点的next就行也就是越过要删除的节点。再把要删除的节点delete。
/*** 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* temp new ListNode;ListNode*cur temp;temp-next head;while(cur-next!NULL){if(cur-next-valval){cur-next cur-next-next;}elsecur cur-next;}head temp-next;delete temp;return head;}
};2. 707设计链表 这道题逻辑很简单但就是很考察指针基本功刚开始写的时候出现了一些指针地址错误改了很多次代码这东西还得多写不然长时间不写真的会生疏最后有个情况测试用例过了但提交失败有错误的情况发现是get函数有问题最后通过打印链表长度发现是addindex这个函数全部插入失败了原因是开始的index合法判断有问题。原本这里用了和get函数一样的index判断。并没有多想但最后出错才发现两个逻辑不一样get函数不允许两个端点的index而addindex却允许有两边的。一个简单的例子现在有三个节点索引是012。此时如果想get索引为3的则应该报错。因为并没有索引3但是如果想要给索引3加节点应该是允许的因为索引3跟原链表是相连的这就是我开始犯的错误没有注意到这一点。最终整体感受这道题对于常写链表代码的人来说。应该会很简单。但对于很长时间没写过链表代码的人来说比如我还是有些复杂的逻辑简单实现有些生疏了。
class MyLinkedList {public:struct ListNode{int val;ListNode* next;ListNode(int val):val(val),next(nullptr){}};MyLinkedList() {head new ListNode(0);size0; }int get(int index) {coutthis-sizeendl;if(index (size-1) || index0){return -1;}else{int now_index0;ListNode*node new ListNode(0);node head-next;while(now_indexindex){node node-next;now_index;}return node-val;}coutthis-sizeendl;}void addAtHead(int val) {ListNode *node new ListNode(val);node-next head-next;head-next node;size;coutthis-sizeendl;}void addAtTail(int val) {ListNode*node new ListNode(val);ListNode*temp head;while(temp-next ! nullptr){temp temp-next;} temp-next node;size;coutthis-sizeendl;}void addAtIndex(int index, int val) {if(index size) return;if(index 0) index 0; int now_index 0;ListNode*node new ListNode(val);ListNode*temp new ListNode(0);temp head;while(now_indexindex){temp temp-next;now_index;}node-next temp-next;temp-next node;size;coutthis-sizeendl;}void deleteAtIndex(int index) {if(indexsize-1)return;int now_index 0;ListNode*node new ListNode(0);node head;while(now_indexindex){node node-next;now_index;}node-next node-next-next;size--;}
private:int size;//记录链表实际长度除头节点外ListNode* head;
};/*** 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);*/
3. 206反转链表 这道题好像是链表的典型题很多面试、链表操作中都会有反转链表的题。具体实现也是有两种方法第一种很简单遍历连边将值重新赋予一个新链表就行最后的新链表就是反转后的链表。当然我们需要掌握的是第二种在原链表的基础上反转这种方法逻辑还是有点抽象的同样是循环每次需要在节点处断开前面待处理的原链表后面是已经反转过的所以肯定需要三个指针一个用来遍历一个用来记录待处理的链表一个指向已经处理后的反转链表。最后将已经处理后的反转链表返回即可对于链表的循环我记得有个很重要的点就是每次循环的操作顺序一定要先记录下一个节点的位置不然更新当前节点的next后则会丢失原本的next在我印象中所有链表操作中这点很重要
/*** 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* temp nullptr; //反转后的ListNode* node head; //遍历用的ListNode* n_node; //待处理的while(node){n_node node-next; //一定优先记录待处理的部分也就是该节点指向当前遍历节点的nextnode-next temp; //进行翻转。当前节点next指向反转后的链表也就是拼接temp node; //更新反转节点的头上一步已经连接的这一步就要把头更新为新节点node n_node; //往前循环}return temp; //最后返回反转链表即可}
};
