行业知识
代码算法训练营day3 | 203移除链表元素、707设计链表、206反转链表
day3:
- 203移除链表元素
- 707设计链表
- 206反转��表
203移除链表元素
题目链接
状态:
文档:programmercarl.com
思路:
有两种办法,一种是不用虚拟头节点,要分两种情况讨论。(删除头节点和非头节点)
一种是用虚拟头节点,不用分情况讨论。
很显然第二种比较方便,并且虚拟头节点也是经常使用的,所以选择用这种方法。
虚拟头节点,顾名思义,就是代替了原有的头节点,所以dummyhead -> next = head;
因为要遍历链表中的每一个元素,来判断是否和要寻找的目标元素的值相等,可以选择一直使用head->next ->value== val;来进行判断,但这样的话head就不能参与判断了,所以又会走入第一种办法的漩涡中。所以这里要添加一个指针cur,指向dummyhead,通过不断的cur->next->value ==val;来进行判断。
代码:
/** * 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* dummyhead = new ListNode(0); //创建虚拟节点 dummyhead->next = head; //让虚拟节点变成虚拟头节点 ListNode* cur = dummyhead; //设置一个临时的遍历变量,指向虚拟头节点 //开始遍历 while(cur!=NULL && cur->next!=NULL) { //如果匹配成功了 if(cur->next->val == val) { ListNode* tmp = cur->next; //保存一下这个节点 //改变目标值前一个值的next的值 cur->next = cur->next->next; delete tmp; //释放目标值 } else{ cur = cur->next; } } //全部遍历完,结果处理 head = dummyhead->next; delete dummyhead; return head; }};注意: 不要忘记最后删除掉虚拟头节点。
707设计链表
题目链接
状态:
文档:programmercarl.com
实现过程中的问题:
①在实现//将一个值插入到下标为index的节点之前 void addAtIndex(int index, int val)函数的时候,忘记了分类讨论:如果index大于链表的长度,则返回空。如果index小于0,则在头部插入节点。
②在实现//删除链表中下标为index的节点 void deleteAtIndex(int index)函数的时候,忘记将创建出来的临时变量用完后置为空,delete命令指示释放了tmp指针原本所指的那部分内存,被delete后的指针tmp的值(地址)并非就是NULL,而是随机值。也就是被delete后,如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针,如果之后的程序不小心使用了tmp,会指向难以预想的内存空间。
代码:
class MyLinkedList {public: // 定义链表结构体 struct LinkedNode { int val; LinkedNode* next; LinkedNode(int val) : val(val), next(nullptr) {} }; MyLinkedList() { // 设置一个虚拟头节点 dummy_head = new LinkedNode(0); size = 0; } // 获取下标为index的节点的值,下标无效返回-1 int get(int index) { if (index (size - 1)) return -1; //dummy_head->next = head; //设定虚拟头节点 // 因为要遍历元素,所以设置一个临时变量cur,指向头节点 LinkedNode* cur = dummy_head->next; //cur指向头节点 while (index--) { //index==0 时跳出while循环 cur = cur->next; } return cur->val; } //将一个值插入到链表中第一个元素之前 void addAtHead(int val) { //变成头节点 LinkedNode* newNode = new LinkedNode(val); newNode->next = dummy_head->next; dummy_head->next = newNode; size++; } //将一个值追加到最后一个元素之后 void addAtTail(int val) { //变成最后一个节点 LinkedNode* newNode = new LinkedNode(val); LinkedNode* cur = dummy_head; while(cur->next!=NULL) //cur的下一个还有数的时候 { cur = cur->next; } //此时cur指向最后一个数 cur->next = newNode; size++; } //将一个值插入到下标为index的节点之前 void addAtIndex(int index, int val) { //也就是插入到index的位置上 if(index > size) return; if(index next; } newNode->next = cur->next; cur->next = newNode; size++; } //删除链表中下标为index的节点 void deleteAtIndex(int index) { if(index >= size || index next指向的节点 while(index--) { cur = cur->next; } //创建新的节点存放被删除的那个节点 LinkedNode* tmp = cur->next; cur->next = cur->next->next; size--; delete tmp; //delete命令指示释放了tmp指针原本所指的那部分内存, //被delete后的指针tmp的值(地址)并非就是NULL,而是随机值。也就是被delete后, //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针 //如果之后的程序不小心使用了tmp,会指向难以预想的内存空间 tmp = NULL; }private: int size; // 链表长度 LinkedNode* dummy_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); */206反转链表
题目链接
状态:
文档:programmercarl.com
思路:
把指针的箭头调个头,就很容易了。代码中实现的是第二行。
因为反转后,原来的节点就有新的next指向的值了,所以要新建一个节点pre去存放每个节点反转后的新的next。
又因为原来节点的next指向改变了,所以需要一个临时指针tmp来存放这个节点原来存放的next的节点,不然到后面节点会丢失。
实现过程中的问题:
①在while循环中,
tmp = cur->next; //存放节点原来的next cur->next = pre; //改变指向//我写把左值和右值写反了,经常会出现这种错误!!!//错误写法:cur->next = tmp;pre = cur->next;
②还是在while循环中,
pre = cur;cur = tmp;//两个赋值顺序写错了,//错误写法:cur = tmp;pre = cur;//很明显就不对,应该在cur被赋值之前就先赋值给pre才行,大意了。
代码:
/** * 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) { //只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表 ListNode* cur = head; ListNode* pre = NULL; //反转后的头节点 ListNode* tmp; //用于存放cur->next while(cur) { tmp = cur->next; //存放节点原来的next cur->next = pre; //改变指向 //pre cur都进行后移 pre = cur; cur = tmp; } //注意pre现在才是我们的头节点,不能再返回head了 return pre; }};总结:
链表问题很有意思,指针的指向也非常灵活,也要记得保存可能会丢失的那个值,很常见的就是cur->next。
上一篇:怎么看服务器公网地址?
下一篇:手机怎么修改网址的域名